% A paper on a multi-commodity market for power load management
% Fredrik Ygge
\documentclass[12pt]{article}
\usepackage{times}
\usepackage{named}
\usepackage{latexsym}
\usepackage{psfig,local}
%\documentstyle[times,psfig,11pt,named,local]{article}
%\documentstyle[psfig,11pt,named,local]{article}
% Note: these are commands specifically defined in local.sty
%\textwidth 12.2cm
%\textheight 19.3cm
\newcommand{\fycom}[1]{{\bf Fredrik comments:} {\em #1}}
\newtheorem{theor}{Theorem}
\newtheorem{tcorr}{Corollary}[theor]
\newtheorem{defi}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{lcorr}{Corollary}[lemma]
\openlinepar
\psdirectories{figs,icmfigs,dadsmfig,c:/text/dadsm-96/figs}
\begin{document}
\title{\bf A Multi-Commodity Market Approach to Power Load Management}
\author{%
{\bf Fredrik Ygge} \footnotemark[2]
\and
{\bf Hans Akkermans} \footnotemark[4]
\and
{\bf Arne Andersson} \footnotemark[3]
}
\date{%
{\small
\footnotemark[2]\
EnerSearch AB and University of Karlskrona/Ronneby \\
Department of Computer Science (IDE) \\
372 25 Ronneby, Sweden \\
Fredrik.Ygge@ide.hk-r.se \\
http://www.rby.hk-r.se/$\ \tilde{}\ $fredriky \\
%
\footnotemark[4]
AKMC and University of Twente \\
Department of Information Systems (INF/IS) \\
P.O. Box 217, NL-7500 AE Enschede, The Netherlands \\
akkermans@ecn.nl, J.M.Akkermans@cs.utwente.nl \\
%
\footnotemark[3]\
Department of Computer Science and \\
Numerical Analysis \\
Lund University \\
Box 118 \\
S-221 00 Lund, Sweden \\
Arne.Andersson@dna.lth.se \\
http://www.dna.lth.se/Arne\_Andersson \\
}
%
\vspace{0.5cm}
{\em Submission for ICMAS '98}
}
\maketitle
\thispagestyle{empty}
\begin{abstract}
\noindent
Power load management is the concept of controlling the loads at the demand side in order to run energy systems more efficiently. Energy systems are inherently highly distributed and contain large number of loads, up to some million. This implies that computationally and conceptually attractive methods are required for this application.
In this paper we give two novel theorems for how to decompose general resource allocation problems into markets. We also introduce a novel multi-commodity market design to meet the demands of power load management. The approach is demonstrated to lead to very high quality allocations, and to have a number of advantages compared to current methods.
\end{abstract}
\noindent
{\bf Topics:} Market-Oriented Programming, Distributed Resource Allocation, Decentralized systems (individual choices driving collective behavior), and Foundations.
\section{Introduction}
Power load management (or load management for short) is the concept of controlling loads at the customer side in order to run energy systems more efficiently. The very basic principle is to try to move load from expensive to less expensive time periods. Time periods can be expensive for many different reasons, stemming from either production or distribution.
When discussing load management, two different categories are normally used~\cite{Flood:92,Ottosson:89,Sorri:92,Wafa:96,Talukdar:87}: \emph{direct} (or utility based), and
\emph{indirect} (customer based, or time-of-use pricing based) . Direct load management is the case where the provider of the electricity controls the loads, subject to some constraints as specified in a contract with the customer. With indirect load management, the customer faces different prices at different times and is itself responsible for making the decisions when to buy. In this paper we focus on direct load management, though most of the presentation is highly relevant for the indirect case as well. We concentrate on load management for the purpose of, e.g., avoiding overheated transformers or optimizing production over time. This in an application with moderate real-time demands.\footnote{Other applications, like oscillation damping (see~\cite{Samuelsson:97}), requires much faster response times and real-time constraints are typically hard. The problems of this kind of applications are, however, fundamentally different from the ones treated in this paper~\cite{Ygge:98Thesis}.}
Contracts with customers can be of many different forms, from contracts allowing the utility to disconnect certain loads during certain time periods for a compensation (such as energy rebate or additional services) to holding the utility is responsible for, e.g., a certain indoor temperature of a building.
Market-oriented programming has been applied to a number of resource allocation applications~\cite{Wellman:93a,Wellman:94a,Wellman:96a,Yamaki:96a,Ygge:96a,Ygge:97MAAMAW,Kurose:89a,Walsh:97}. The basic idea is that computational \emph{agents} trade resource with each other through \emph{auctions} using concepts from economics, such as prices, demands and general equilibrium.
In our research so far (see, e.g.,~\cite{Ygge:96a}), we have used a market-oriented approach to load management with only two commodities -- money and the active power for the upcoming time-period, e.g. hour. We have also only run simulations of very idealized load models~\cite{Ygge:96a}. The contributions of this paper are 1) two novel theorems about the relation between optimization and markets, 2) generalization to a multi-commodity market for load management, 3) incorporation of realistic load models, and 4) introduction of a method for performing on-line cost/benefit analysis for every load management contract in the entire energy system.
The paper is organized as follows. In Section~\ref{sec:theory}, some theory on the relations between optimization and markets is introduced. The market design is described in Section~\ref{sec:design} and it is exemplified in Section~\ref{sec:example}. A method for performing cost/benefit analysis for each contract in introduced in Section~\ref{sec:costBenefit}. The issue of the existence of a market equilibrium for this application is discussed in Section~\ref{sec:eqEx}, and, finally, Section~\ref{sec:concl} concludes.
\section{Theory for Applying Markets to Optimization Problems}
\label{sec:theory}
In this section we give some general theory for the relation between very general resource allocation problems and a certain market configuration consisting of consumers and producers. Definition~\ref{defi:MP} describes the general resource allocation problem. Definition~\ref{defi:M} describes how the general resource allocation problem can be decomposed into a specific market configuration. Theorem~\ref{theor:pareto} states that any Pareto optimal allocation in this market is an optimal solution to the general resource allocation problem. Finally, Theorem~\ref{theor:compEqOpt} states that also the competitive equilibrium is an optimal solution.
\begin{defi}
The maximization problem \emph{MP} is given by
\begin{equation}
\begin{array}{ll}
\max_{\mathbf r} & \sum_{i=1}^n f_i({\mathbf r}_i) \\
s.t. & \sum_{i=1}^n {\mathbf r}_i = {\mathbf R}, \,\, \forall {\mathbf r}, \\
& r_{ij}^l \leq r_{ij} \leq r_{ij}^u
\end{array}
\label{eq:resAlloc}
\end{equation}
${\mathbf r}_i = [r_{i1}, r_{i2},\ldots , r_{ik}]$, $r_{ij} \in S_{ij}$, $r_{ij}^l \in S_{ij}$, $r_{ij}^u \in S_{ij}$, ${\mathbf r} = [{\mathbf r}_1, {\mathbf r}_2,\ldots , {\mathbf r}_n]$, $f_i: {\mathbf S}_i \mapsto \Re$, and $S_{ik}$ is any set of reals (e.g., all reals, all positive integers or $\{1.25, 2.77, 4\frac{1}{3}\}$). The problem is interpreted as a resource allocation problem and $f_i({\mathbf r})$ is interpreted as the value of allocating ${\mathbf r}$ to node $d_i$.
\label{defi:MP}
\end{defi}
\begin{defi}
With the notation from \emph{MP}, the market \emph{M} is a market of $n$ agents, in which all nodes, $d_i$, such that $\exists j$, $r_{ij}^l < 0$, are modeled as \emph{profit maximizing producers}~\cite[pp.~135-137] {Mas-Colell:95a} solving the problem
\begin{equation}
\max_{{\mathbf r}^\circ} {\mathbf p} \cdot {\mathbf r}^\circ + f_i^\circ({\mathbf r}^\circ),
\label{eq:genProd}
\end{equation}
where ${\mathbf p} = [p_1, p_2,\ldots , p_k] \in \Re^k$ denote the respective market price for the $k$ commodities, ${\mathbf r}^\circ$. ${\mathbf r}^\circ$ is a \emph{delivered} amount of resource whereas ${\mathbf r}$ is defined as an \emph{allocated} amount, i.e. ${\mathbf r}^\circ = -{\mathbf r}$. $f_i^\circ({\mathbf r})$ is defined by $ f_i^\circ({\mathbf r}^\circ) = f_i({\mathbf r})$.
Furthermore, all nodes, $d_i$, such that $\neg \exists j$, $r_{ij}^l < 0$, are modeled as \emph{utility maximizing consumers}~\cite[pp.~17 -- 39, p.~314]{Mas-Colell:95a} holding a \emph{utility function}~\cite[Definition 1.B.2, p.~9]{Mas-Colell:95a} defined by
\begin{equation}
u_i({\mathbf r}_i,m_i) = f_i({\mathbf r}_i) + m_i,
\label{eq:quasiLin}
\end{equation}
$m_i \in \Re$, i.e. $ u_i({\mathbf r}_i,m_i)$ is \emph{quasi-linear}~\cite[Definition 3.B.7, p.~45]{Mas-Colell:95a} with respect to $m_i$.
Furthermore, in \emph{M}, $\sum_{i=1}^n m_i = 0$, $\forall {\mathbf m}$, ${\mathbf m} = [m_1, m_2,\ldots ,m_n]$, and $\sum_{i=1}^n {\mathbf r}_i = {\mathbf R}$, $\forall {\mathbf r}$. Let the market price of $m$ be $1$.
\label{defi:M}
\end{defi}
\begin{theor}
Any \emph{Pareto-optimal allocation}~\cite[Definition 10.B.2, p.~313]{Mas-Colell:95a} in $M$ is a solution to $MP$.
\label{theor:pareto}
\end{theor}
{\bf Proof} A producer in $M$ is behaviorally equivalent to a "consumer" with the utility function of Eq.~(\ref{eq:quasiLin}), which is allowed to have $r_{ij}^l < 0$. (The maximization problem of the producer, Eq.~(\ref{eq:genProd}), can be rewritten as $\max_{\mathbf r} f_i({\mathbf r}) - {\mathbf p} \cdot {\mathbf r}$. Since a consumer can buy $m$ for $p_ir_i$ the statement follows.) Let $\Delta f = \sum_{i=1}^n f_i({\mathbf r}_i^b)-f_i({\mathbf r}_i^a)$.
For any allocation $\langle {\mathbf r}^a,{\mathbf m}^a \rangle$ in $M$,
$\langle {\mathbf r}^b,{\mathbf m}^b \rangle$
(where $m_i^b = m_i^a+u({\mathbf r}_i^a,m_i^a)-u({\mathbf r}_i^b,m_i^a)+\frac{\Delta f}{n}$,)
is a Pareto-improvement if $\Delta f > 0$.
($\sum_{i=1}^n m_i^b = 0$, because
$\sum_{i=1}^n u_i({\mathbf r}_i^a,m_i^a)-u_i({\mathbf r}_i^b,m_i^a) = -\Delta f$.)
In other words: if an allocation is not a solution to $MP$ it is not Pareto-optimal in $M$.
Thus, if an allocation is Pareto-optimal in $M$ it is a solution to $MP$.
$\Box$
\begin{theor}
If there exists a \emph{competitive equilibrium}~\cite[Definition 10.B.3, p.~314]{Mas-Colell:95a} in $M$ then this is a solution to $MP$.
\label{theor:compEqOpt}
\end{theor}
{\bf Proof} Since the competitive equilibrium is Pareto-optimal (see, e.g.,~\cite[p.~766]{Mas-Colell:95a} or~\cite[p.~192]{Takayama:85a} -- every point in $M$ is trivially non-satiated because of $m$) we have from Theorem~\ref{theor:pareto} that it is a solution to $MP$.
$\Box$
Even though not as explicit and general as Theorem~\ref{theor:pareto} and Theorem~\ref{theor:compEqOpt}, strongly related theory and thoughts are found in \cite{Bikhchandani:97} and \cite{Walsh:97} for the special case of exchange markets.
\section{A Multi-Commodity Market Design for Load Management}
\label{sec:design}
This section describes our market design for load management. The important design issues are the definition of the commodities, the agents, and the agent interaction.
\subsection{Commodities}
The power of different time slots represent the different commodities. The approach presented is not limited to any special division of time or number of commodities. For example, one could consider using $15$ minute time slots the first hour, $30$ minute time slots the next $2$ hours, $1$ hour slots for the following $5$ hours, and $4$ hour time slots for the following $40$ hours, i.e. a market of $23$ commodities over a total time period of $48$ hours. Of course, the finer grained the time scale (larger number of commodities), the more accurate outcome, but also the heavier computational burden.
For the prices and demands of the next few periods to be \emph{exactly} correct a market with an infinite number of commodities, covering time infinitely into the future, is required. Since this is practically impossible, we set up a reasonable number of commodities, e.g., the $23$ commodities described above, and let the agents base their decisions of these time periods on some rough estimations of future values, i.e. for the example here, rough estimates of the prices of the $49$th hour and beyond. In this paper we will let the estimate be the price of the last time period covered by the market, though other alternatives are certainly conceivable~\cite{Ygge:97Tech}.
Auctions (further described below) can be performed regularly or when required. Typically, with the market setting defined above, a new auction would be performed every $15$th minute. The reallocation of resource is performed as described by the bids of the upcoming time period. The future prices and allocations are established for two reasons: 1) the price and demand for the upcoming period can not be established without knowledge about future prices, and 2) the estimates of future prices and demands is useful information for the utility. The market outcome provides the utility with a control strategy for the upcoming time period and useful predictions about future prices and demands in a compact and uniform manner.
\subsection{Agents}
Each load in the system is represented by a computational agent, a \textsc{Homebot}. The responsibility of a \textsc{Homebot} is to use electricity as efficient as possible given: the customer preferences, the load state, consumption predictions, and the load model. The \emph{customer preferences} are represented by a customer contract. The indoor temperature of a building, or the amount of warm water in a warm water heater are examples of the \emph{load state}. The \emph{consumption predictions} are preprogrammed or learned consumption patterns. Physical load characteristics, such as time constants, are contained in the \emph{load model}.
A \textsc{Homebot} is modeled as a consumer which preferences are modeled by a quasi-linear utility function defined by
\begin{equation}
u_\alpha({\mathbf r},m) = f_\alpha({\mathbf r}) + m,
\label{eq:hbUtil}
\end{equation}
where ${\mathbf r} = [r_1, r_2, \ldots , r_k]$ is the resource (active power) of the different time intervals ($1 \ldots k$), $f_i({\mathbf r})$ represent the profit, or cost (negative profit), associated with ${\mathbf r}$, i.e. it captures the customer preferences, the load state, consumption predictions, and the load model. The money, $m$, is corresponds to a real currency, such as SEK.
The task of each \textsc{Homebot} is to maximize its utility through trade with other agents. In such trade the \textsc{Homebots} are programmed to act \emph{competitively} (equivalent to acting as a \emph{price-taker})~\cite[p.~20, p.~314]{Mas-Colell:95a}, i.e. treat prices as exogenous, rather than speculate about the effects of its own action on market prices (\emph{cf.}~\cite{Sandholm:97a}).
Also uncontrollable loads are represented by \textsc{Homebots}. In this case, however, the \textsc{Homebot} is totally insensible to prices. Such a \textsc{Homebot} can represent one or a number of loads. A \textsc{Homebot} representing an uncontrolled load utilize a suitable method for prediction, see e.g. ~\cite{Holst:77,Holst:87,Avilla:94,Kulkarni:96}.
Agents representing production units are modeled as profit maximizing producers, i.e. they solve the maximization problem:
\begin{equation}
\max_{\mathbf r} {\mathbf p} \cdot {\mathbf r} - cost_\alpha({\mathbf r}),
\label{eq:prodMax}
\end{equation}
where ${\mathbf r}$ is a \emph{produced} amount of resource, and $cost_\alpha({\mathbf r})$ is producer $\alpha$'s cost associated with producing ${\mathbf r}$.
Also the production agents are programmed to act competitively.
In ~\cite{Ygge:97Tech} we also describe how agents for distribution and external markets are modeled.
\subsection{Agent Interaction and Structure}
The agents interact through \emph{auctions}. In an auction agents submit competitive bids and the auctioneer computes a general equilibrium (i.e. a set of prices such that supply meets demand for each commodity). When market equilibrium has been obtained, the resource is allocated.
\postscript{10cm}{struct}{\em \small A typical structure of a load management system. The \textsc{Homebots} are connected to auctioneers which, in turn, are connected to other auctioneers in a hierarchic manner.}
The structure of the load management system is typically as in Figure~\ref{fig:struct}. The power distribution system is inherently very hierarchic, and the structure of the load management system normally reflects this.
\section{A Load Management Example}
\label{sec:example}
We will now demonstrate the market design on a particular example. The example includes one production unit, $9$ warm water heaters, one public building and a number of uncontrollable loads as depicted in Figure~\ref{fig:prodopt}.
\postscript{10cm}{prodopt}{\small \em A small part of an energy system -- a producer and its customers.}
\subsection{Load and Production Characteristics}
We investigate a $4$ hour time period which can be thought of as morning hours where many people have taken morning showers and have gone to work. We assume that there is no consumption during the investigated time period. Thus, the heaters will at this point start to heat water until they are fully heated. The utility has a contract with each customer allowing the utility to switch off the loads for a certain amount of time during the $4$ hour period. The interesting parameters for each load is how much it consumes when it is switched on, how much energy it is expected to need to be fully heated, and for how long it can be disconnected. The controllable loads of this example are described in Table~1.
\begin{table}[htb]
{\small
\begin{center}
\begin{tabular}{||r|r|r|r|r||} \hline \hline
Type & Power (kW) & Need (kWh) &Time (h)\\ \hline
$1$ & $2$ & $4$ & $1$ \\ \hline
$2$ & $3$ & $5$ & $1/2$ \\ \hline
$3$ & $1$ & $2$ & $1$ \\
\hline \hline
\end{tabular}
\end{center}
\caption{\em The loads of the example. The columns describe, from left to right, a type name, the power consumption when switched on, the current need, and the time that the load can be disconnected during the $4$ hours.}
}
\end{table}
In addition to the water heaters, there is a public building supplied by the producer. It is assumed that the utility has a contract with the customer making the utility responsible for the indoor temperature of the building. At a sample interval of $1$h, the temperature of the building is a function of the resource as described by (\emph{cf.} \cite{Ygge:97MAAMAW})
\begin{equation}
\begin{array}{l}
t_i = t_{i-1}-0.1(t_i-10)+10^{-2}r_i \Leftrightarrow \\
t_i = \frac{1}{1.1}\left(t_{i-1}+1+10^{-2}r_i\right).
\end{array}
\label{eq:houseTemp}
\end{equation}
$t_0$ is assumed to be $19^\circ C$.
The heating system includes radiators of a total power of $300$kW. There is a lower constraint of $10$ for how little resource the building can be assigned at the investigated time periods. (This lower constraint is often included in load management contract in order to avoid unpleasant draft from windows etc.) Thus, $10 \leq r_i \leq 300$, $\forall i$, for the building.
There is a contract between the utility and the customer stating that the utility is responsible for maintaining the indoor temperature $20^\circ C$ for a certain annual fee. The utility must pay the customer a compensation for deviation from the agreed on temperature of
\begin{equation}
c_{cust}(t_i) = 10 \cdot \left(t_i-20\right)^2,
\label{eq:houseCost}
\end{equation}
for every sample $t_i$ at a $1$ hour sample period.
In addition to the controllable loads there are some uncontrollable loads with the expected consumption $10$, $400$, $100$ and $80$ for each of the coming next $4$ hours.
The production cost is assumed to be
\begin{equation}
c_{prod}(r_i) = 10^{-3} r_i^2
\label{eq:prodCust}
\end{equation}
\subsection{The \textsc{Homebots} and the Production Agent}
We analyze a market of $4$ commodities, representing $1$ hour each. In this example the \textsc{Homebots} representing the warm water heaters will have a utility function as described by Eq.~(\ref{eq:hbUtil}) with $f_i({\mathbf r}) = 0$ when the consumption is such that the disconnection time, as defined in Table~1, is not violated, and $f_i({\mathbf r}) = -C$, where $C$ is a large constant, otherwise. That is, as long as the contracted disconnection time is not violated, there is no cost for the load management, but if the contract is violated, there is a very high cost. We assume every agent to have a perfect estimate of its future need. This is not required for the approach to work, but it simplifies the computations. If uncertainty about the need is present, the \textsc{Homebot} should instead base its action on probability distributions of the need. As all the need is always satisfied within the $4$ hours covered by the market, regardless of how the load contracts are utilized, future prices do not affect current demands. Thus, no predictions of price for hour $5, 6,$ and so on, are required.
From Eq.~(\ref{eq:houseTemp}) and Eq.~(\ref{eq:houseCost}), we see that the cost for deviation from the set-point temperature of the building can be expressed as a function of $t_0$ and ${\mathbf r}$. Hence, the utility function of the \textsc{Homebot} responsible for the building is
\begin{equation}
u_b({\mathbf r},m) = -\sum_{i=1}^k c_{cust}(t_0,{\mathbf r})+m.
\label{eq:ex2BuildUtil}
\end{equation}
In this case the demands of the $4$ time periods are dependent on future prices. If the price for the $5$th hour is extremely high the demand during the $4$ hours covered by the market will increase, and vice versa. We assume the price of all future time periods (not covered by the market) to be the same as the price of the last hour covered by the market. We have empirically found that it is practically sufficient to consider $4$ additional hours after the ones covered by the market for this example.
The uncontrollable loads are represented by a \textsc{Homebot} with the demands $10$, $400$, $100$ and $80$ for the respective time intervals, independently of prices.
\subsection{The Market Outcome}
The above agents were implemented together with an auctioneer using a price-oriented Newton scheme~\cite{Ygge:98Thesis}.
\postscript{10cm}{res}{\small \em The used resource in different time periods with and without load control. The result of the load control is that load is moved from period two to the other periods.}
In Figure~\ref{fig:res} the allocations in presence and absence of load management are compared.\footnote{When load management is not present, the building is assumed to have a control system that maintains $20^\circ C$. The corresponding resources for doing this is (see Eq.~(\ref{eq:houseTemp})) $200$, $100$, $100$, and $100$.} We see that the result is a shift of load from time period $2$ to the other periods. The corresponding market prices are shown in Figure~\ref{fig:price}. The market price of time period $2$ has been reduced significantly. However, it is still significantly higher than the prices of time period $1$, $3$, and $4$, and it could be profitable to arrange load management contracts with more customers in order to shift more load from time period $2$ to periods $1$, $3$, and $4$, \emph{cf.} Section~\ref{sec:costBenefit}.
\postscript{10cm}{price}{\small \em The market prices (the marginal production cost) of the different time periods. The market price of time period two has been reduced significantly.}
\begin{table}[htb]
{\scriptsize
\begin{center}
\begin{tabular}{||l|r|r|r|r||r|r|r|r||} \hline \hline
& \multicolumn{4}{|c|}{Uncontrolled} & \multicolumn{4}{|c|}{Controlled} \\ \hline \hline
Type & $r_1$ (kW) & $r_2$ (kW) & $r_3$ (kW) & $r_4$ (kW) & $r_1$ (kW) & $r_2$ (kW) & $r_3$ (kW) & $r_4$ (kW) \\ \hline
$1$ & $2$ & $2$ & $0$ & $0$ & $2$ & $0$ & $2$ & $0$ \\ \hline
$2$ & $3$ & $3$ & $0$ & $0$ & $3$ & $1.5$ & $1.5$ & $0$ \\ \hline
$3$ & $1$ & $1$ & $0$ & $0$ & $1$ & $0$ & $1$ & $0$ \\ \hline
Building & $200$ & $100$ & $100$ & $100$ & $211.8$ & $10$ & $119.5$ & $125.2$ \\ \hline
Uncontrollable & $10$ & $400$ & $100$ & $80$ & $10$ & $400$ & $100$ & $80$ \\ \hline
Total & $228$ & $515$ & $200$ & $180$ & $239.8$ & $414.5$ & $229.99$ & $205.2$ \\
\hline \hline
\end{tabular}
\end{center}
\caption{\em The allocations of the example. Note that the lower resource limit of the building is $10$ and that loads of type $2$ can only be controlled for $30$min. When considering the total resource, keep in mind that there are three loads of each type $1$, $2$, and $3$.}
}
\end{table}
As seen from Table~2, as little resource as possible is used for time period $2$ by all involved controllable loads.
\postscript{10cm}{temp}{\small \em The temperature of the public building. In order not to have a too big deviation from the agreed on temperature during period $2$, when the resource is very scarce, the temperature is set above the set point in period $1$.}
The temperature of the public building is plotted in Figure~\ref{fig:temp}. The most interesting thing of this figure is maybe that the \textsc{Homebot} of the building has found that the optimal choice is to buy so much resource during time period $1$ so that the temperature temporary is \emph{above} the set point even though this leads to a penalty. This control scheme is found in previous approaches to load management, e.g.,~\cite[pp.~33 -- 35]{Larsson:88}. In~\cite{Larsson:88}, however, the scheme was hard-coded for certain hours each day, and in the present work it was the optimal choice in a certain situation; at another occassion it might be completely different.
From Theorem~\ref{theor:compEqOpt} we know that the market outcome is the optimal solution, given the current information and time division.\footnote{Strictly speaking, the \emph{true} market equilibrium is the optimal solution. As the utilized algorithm only computes an approximation of this equilibrium, we only obtain an approximate solution. However, the sum of the absolute value of the excess demand for every commodity was in the order of $10^{-7}$ in the simulation, so the approximation is indeed very accurate.} The total cost without load management is $389.61$ (the production cost) and the cost with load management is $332.33$.\footnote{Even though the cost of the four periods is a highly relevant measure, it is not the entire truth. If the \textsc{Homebot} of the building only considers the four periods, without taking further periods into account, the cost would be lower. However, this would be sacrificing the future for the present. The presented result are optimal when taking the future into account as described by the predictions of future prices.} The latter is the production cost plus the compensation to the customer because of temperature deviations. The compensation of this example is $8.01$.
\section{Cost/Benefit Analysis}
\label{sec:costBenefit}
Since every agent is facing the market price, it is able to compute an approximate value of its \emph{profits} from the ability to control its load. If consequences on prices of the action of a single agent can be neglected, the profit is simply the cost for the consumed energy if the load was not controllable minus the cost when it was controlled.
As an example, consider a load of type $1$ in the example above. If the agent's effect on prices is negligible, the profit (resulting from moving $2$kW from period $2$ to period $3$) is $2 \cdot p_2 - 2 \cdot p_3 = 0.77$. The \emph{actual} profit is the cost for the utility when the load is not controllable (i.e. is belonging to the uncontrollable loads) and the cost when the load is controllable. A simulation of the type in the example was performed with one of the loads of type $1$ considered as a uncontrollable load with consumption $[2,2,0,0]$. That results in a total cost of $333.10$ (of which $7.99$ is compensation to the customer for temperature deviations of the public building)\footnote{It might come as a surprise that the compensation to the customer dropped from $8.01$ to $7.99$ (when disabling the control of one of the loads), meaning that the building was less disturbed with fewer controllable loads. The reason is that disabling the control here caused a drop of price $3$ and a rise of price $2$. Since the building is already at its lower limit during period $2$, it will be less controlled during period $3$ but equally controlled at period $2$.}. From above we have that the cost when the load is controllable is $332.33$. That is, the actual profit is $333.10 - 332.33 = 0.74$. Thus, even for this relatively small market the local estimation was quite accurate, and the less effect a single agent has on prices, the more accurate the estimate will be.
The local estimates provide the utility with extremely useful information. For each load in the system, an estimate of the value of the current load management contract is obtained. If a contract is generating less money than it costs, the utility has too many of these kind of contracts. In this situation the utility might gain money by lower the compensation for this type of contract, even if a number of customers are not willing to participate at the new lower compensation. Correspondingly, if the money generated by the contract is greater than the cost for it, the utility might profit by rising the price and hereby get more customers participating in the load management program.
\section{The Existence of Equilibrium}
\label{sec:eqEx}
In the above example, the equilibrium existed. However, since the demands resulting from competitive behavior of the \textsc{Homebots} representing the warm water heaters are discontinuous, the equilibrium is not guaranteed to exist in the general case. On the other hand, in load management, the number of agents is very large (up to some million) and they hold very different utility functions. Then a certain insight from micro-economic theory turns out to be highly relevant: the larger the number of agents, and the more heterogeneous they are, the larger the chance that a general equilibrium exists~\cite[p.~627--630]{Mas-Colell:95a}. Furthermore, a very small modification of the behavior of the \textsc{Homebots} of this example can be implemented so that the general equilibrium is \emph{guaranteed to exist} without affecting the optimality of the outcome in any significant way~\cite{Ygge:97Tech}.
\section{Conclusions}
\label{sec:concl}
In this paper we gave two novel theorems on how to decompose general resource allocation problems into markets. We also introduced a novel multi-commodity market for load management. We claim that this approach to load management has a number of advantages compared to current methods (such as~\cite{Wafa:96,Popovic:97,Talukdar:87,Larsson:88,Karlsson:89}):
\begin{enumerate}
\item \label{it:int} It provides an integrated strategy for many different types of loads and contracts. From low level contracts allowing the utility to switch off loads for certain amounts of time to high level services, like indoor temperature control.
\item \label{it:opt} The outcome is of very high quality, typically a very close approximation of the theoretical optimum is obtained.
\item \label{it:decomp} It enables natural decomposition, both from a software engineering perspective as well as from a computational perspective. All local characteristics are encapsulated by agents, communicating only through prices and demands while doing local optimization computations.
\item \label{it:eff} It can be efficiently implemented (for the two commodity case, see, e.g.,~\cite{Ygge:96a,Andersson:98a}, and for the multi-commodity case, see, e.g.,~\cite{Ygge:98ICMASAny,Ygge:98ICMASRes,Ygge:98Thesis}).
\item \label{it:abstr} The main abstractions used, price and demand, or probably the most natural abstractions to use for a utility.
\item \label{it:uniform} The utility is provided with a compact and uniform estimate of the energy system characteristics (present and future) in terms of prices and demands.
\item \label{it:local} A local estimate of the value of the load management contract is obtained. This enables the utility to do continuous on-line cost/benefit analysis of every load management contract in the entire system.
\end{enumerate}
Clearly, it can be argued that there might be competing approaches (from, e.g., (distributed) mathematical optimization or resource allocation) that can be applied to load management fulfilling items (\ref{it:int}), (\ref{it:opt}), (\ref{it:decomp}), and (\ref{it:eff}). The problem does not necessarily have to be modeled as a market in order to set up utility functions and maximize the sum of them in a distributed fashion. (For example, a non-market interpretation of Theorem~\ref{theor:compEqOpt} is given in~\cite{Andersson:97Tech}.) We do not disagree with such a position, but argue that the integrated view of all types of loads and contracts, the high quality outcome, the computational and conceptual decomposition of the global problem into small pieces of locally optimizing software, and the efficient algorithms, together form a novel approach to load management. This holds regardless of if our approach is described with classical mathematical optimization and resource allocation concepts or if it is treated with market abstractions.
Our main arguments for a market view of the system are items (\ref{it:abstr}), (\ref{it:uniform}), and (\ref{it:local}). We believe the naturalness of the approach to be of vital importance. The successful integration of a load management system in the core business information management of a utility is heavily dependent on how the system is appreciated by the people in the organization. The personnel responsible for the energy trade a very familiar with concepts such as demand and prices. Therefore, the metaphor of local agents "negotiating" over power and hereby obtaining market equilibrium is a very attractive one which simplifies the understanding of the principles of the system. The issue of naturalness is also important from the software engineering perspective. Along the same line of reasoning, the estimate of the energy system characteristics in terms of prices and demands is probably the most useful one for the utility. Furthermore, well known concepts from economics, such as price elasticity are directly applicable. Finally, the feature of local evaluation of load contracts for every load in the entire system is only inherent in a market approach, and we believe it to be extremely useful.
\bibliography{ygge}
%\bibliographystyle{unsrt}
\bibliographystyle{named}
\end{document}