% Article for Journal of Artificial Intelligence Research
% Draft version June 16th, 1998
% Second Draft 24 August 1998
% Revision after review 30 October 1998 
% Resubmission version completed 16 March 1999
% Revision after review 2 May 1999
% Further revised 17 July 1999 JMA
% Fredrik Ygge and Hans Akkermans
% Final editor comments taken care of 13 Sept. 1999 Ygge


\documentclass[11pt,twoside]{article}
\usepackage{jair,theapa,ifthen,psfig,latexsym}
%\documentstyle[jair,twoside,11pt,theapa,ifthen,psfig]{article}
\input epsf %% at top of file

%From Tel via Weiss:
\def\algorithmname{Algorithm}
\newenvironment{algorithm}[2]{\begin{figure}[bt]
        \def\figurename{\algorithmname}
        \def\floattext{#2}\def\floatlabl{#1}
        \rule{\columnwidth}{0.2mm}
        \begin{tabbing}}{
        \end{tabbing}
        \caption{\sc\floattext}\label{\floatlabl}
        \rule{\columnwidth}{0.2mm}\end{figure}}

%\jairheading{1}{1993}{1-15}{6/91}{9/91}
\jairheading{11}{1999}{301-333}{3/99}{10/99}

\ShortHeadings{Decentralized Market Control}
{Ygge \& Akkermans}
\firstpageno{301}

\title{\bf Decentralized Markets versus Central Control: \\ 
           A Comparative Study}

\author{\name Fredrik Ygge 
		\email ygge@enersearch.se \\
		\addr EnerSearch AB and Uppsala University \\
                Chalmers Science Park \\
		S-412 88 Gothenburg, Sweden\\
		www.enersearch.se/ygge\\                
              \AND
                \name Hans Akkermans
		\email HansAkkermans@cs.vu.nl \\
                \addr AKMC and Free University Amsterdam\\
                Department of Information Management and Software Engineering \\
                Computer Science Division \\
                De Boelelaan 1081a, NL-1081 HV Amsterdam, The Netherlands \\
}


\date{DRAFT \today}

\newtheorem{definition}{Definition}[section]
\newtheorem{axiom}{Axiom}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
%\newtheorem{algorithm}{Algorithm}[section]

\newenvironment{example}{\noindent {\bf Example. }}{}

\newenvironment{proof}{\noindent {\bf Proof. }}{$\Box$ \vspace{0.11in} \\}

\newenvironment{counterexample}{{\bf Counterexample. }}{}

\begin{document}
\maketitle

% -------------------
% Command definitions
% -------------------

\newcommand{\argmax}[1] {\arg \hspace{-0.04in} \max_{{}_{#1}}}
\newcommand{\argmin}[1] {\arg \hspace{-0.04in} \min_{{}_{#1}}}

\newcommand{\ttchoose}[2] {\left( \begin{array}{c} {#1} \\ {#2} \end{array} \right)}

\newcommand{\ttalts}[4] {\left\{ \begin{array}{ll} {#1}   & \mbox{#2} \\
                                                  {#3} & \mbox{#4}
                                 \end{array} \right. }
\newcommand{\sij}[2] {\left. \begin{array}{ll} {}   & \mbox{#1} \\
                                               {}   &  {}       \\
                                               {}   & \mbox{#2}
                                 \end{array}
                         \right| }

\newboolean{printcomments}
\setboolean{printcomments}{true}
%\setboolean{printcomments}{false}

\newcommand{\fycom}[1]{
\ifthenelse{\boolean{printcomments}}{{\bf Fredrik comments:} {\tt  #1}} {}
}
\newcommand{\hacom}[1]{
\ifthenelse{\boolean{printcomments}}{{\bf Hans comments:} {\tt  #1}} {}
}
\newcommand{\fyrep}[3]{
\ifthenelse{\boolean{printcomments}}{{\bf Fredrik suggests, replace:} { \tiny #1}{\bf  with:} #2 {\bf Reason:} {\tt #3}} {{\bf Tentative text: } #2 {\bf end of tentative text}}
}
\newcommand{\harep}[3]{
\ifthenelse{\boolean{printcomments}}{{\bf Hans suggests, replace:} { \tiny #1}{\bf  with:} #2 {\bf Reason:} {\tt #3}} {{\bf Tentative text: } #2 {\bf end of tentative text}}
}
\newcommand{\old}[1]{
\ifthenelse{\boolean{printcomments}}{{\bf \tiny Old or additional text of potential interest:} {\tiny  #1}}{}
}
\newcommand{\revcom} [2]{\noindent {\bf Comment by #1:} {\it #2}}
\newcommand{\reply} [1]{\noindent {\bf Our reply:} #1}


\sloppy

\begin{abstract}
Multi-Agent Systems (MAS) promise to offer solutions to problems where
established, older paradigms fall short. In order to validate such claims that are repeatedly made in software agent publications,
empirical in-depth studies of advantages and weaknesses of multi-agent 
solutions versus conventional ones in practical applications are
needed. Climate control in
large buildings is one application area where multi-agent systems, and market-oriented
programming in particular, have been reported to be very successful, although central control solutions are still the standard practice.
We have therefore constructed and implemented a variety of market
designs for this problem, as well as different standard control
engineering solutions. This article gives a detailed analysis and
comparison, so as to learn about differences between standard versus
agent approaches, and yielding new insights about benefits and
limitations of computational markets. An important outcome is that ``local information plus market communication produces global control''. \end{abstract}

\section{Introduction}

When new paradigms arise on the scientific horizon, they must prove
their value in comparison and competition with existing, more
established ones. The multi-agent systems (MAS) paradigm is no exception. In a
recent book on software agents
\cite{Bradshaw:97a}, Norman observes that perhaps ``the most relevant
predecessors to today's intelligent agents are servomechanisms and
other control devices''. And indeed, a number of applications for
which multi-agent systems have recently claimed success, are close to the realm of
what is traditionally called control engineering. One clear example is
the climate control of large buildings with many office rooms. Here,
Huberman \& Clearwater \citeyear{Clearwater:94a,Huberman:95a} have constructed and tested a working
MAS solution based on a market approach, that they reported to
outperform existing conventional control.

The key question studied in this article is: \emph{in what respect and to what extent are multi-agent
solutions better than their (conventional) alternatives?} We believe that the
above-mentioned application provides a nice opportunity to study this
question in a detailed empirical way. It is practically very relevant, it lends
itself to alternative solutions, and it is quite prototypical for a
wide range of industrial applications in distributed resource allocation
(including energy management applications
\cite{Ygge:96a,Akkermans:97DADSM,Ygge:98ICMAS}, telecoms applications, the file allocation problem of Kurose and Simha
\citeyear{Kurose:89a}, and the flow problems investigated by Wellman
\citeyear{Wellman:93a}).

This article gives a detailed analysis of a published
MAS solution to building climate control, and it compares multi-agent markets with traditional control approaches. We also introduce an improved and novel multi-agent solution to this problem based on an equilibrium market. From our comparative analysis we are able to draw general conclusions about
the suitability of the various approaches. Briefly, we show how  computational markets can be designed that perform as well as centralized controllers having global information about the total system. However, a major advantage of the market framework is that it  achieves this in a fully decentralized fashion using only locally available data. We finally outline that it should be possible to come to a more general theory concerning the connections between markets and conventional control concepts. Here, we show that for the considered type of applications the quasi-equation \emph{``local data + market communication = global control''} holds.

The structure of the article is as follows. After an introduction (Section~\ref{sec:mop}) to market-oriented programming and available theory, Section~\ref{sec:problemDef} gives the problem definition. Section~\ref{sec:office}
introduces the application domain: it describes the office environment and
gives the physical model for cooling power and the various temperature
and outside weather influences. We then discuss the results of a standard control
engineering solution, based on local and independent integral
controllers regulating the building climate (Section~\ref{sec:controlA}). Next, we review the
market-based approach as put forward by Huberman \& Clearwater 
\citeyear{Clearwater:94a,Huberman:95a} (Section~\ref{sec:marketA}), and validate their claim that this market approach performs better than conventional independent controllers. We subsequently analyze this market protocol in detail and show that its success is related to the fact that the agents possess global information before the auction is started (Section~\ref{sec:marketAP}). In Section~\ref{sec:controlB} we then develop an improved standard control engineering scheme that also exploits global data. Such a control scheme turns out to perform much better than the Huberman-Clearwater market.
Finally, we propose a market design of our own based on general equilibrium theory. It performs as well as the controller having access to global data, but operates on local data only and thus represents a really decentralized solution (Section~\ref{sec:marketB}). Section~\ref{sec:conclusions} puts our
results into perspective and summarizes the general conclusions in comparing different approaches.

\section{Market-oriented Programming}
\label{sec:mop}

The use of market mechanisms for resource allocation by computer systems has a rather long history in computer science, e.g.~\cite{Sutherland:68Futures}, and more recently markets have been used in a number of different application areas.
 
\newpage

There is rather extensive theory available for the relations between optimization and markets. For example:
\begin{itemize}
\item Jennergren~\citeyear{Jennergren:73Price} has shown how a price schedule decomposition algorithm can be used for solving linear programming problems.
\item Kurose \& Simha~\citeyear{Kurose:89a} showed how an equilibrium constitutes an optimal solution to a file allocation problem. A similar result was shown by Bertsekas~\citeyear{Bertsekas:92Auction} for the assignment problem.
\item Bikhchandani \& Mamer~\citeyear{Bikhchandani:97} showed that a Pareto efficient outcome\footnote{An allocation is Pareto efficient or Pareto optimal if there is no alternative allocation that makes any agent better off without making the outcome worse for some other agent~\cite[p.~15]{Varian:96a}.} maximizes the sum of the utilities in an exchange market with agents holding quasi-linear utility functions\footnote{An example of a quasi-linear utility function is given in Eq.~(\ref{eq:properUtility}).} This is a significant extension to the above, as it also applies to non-linear problems.\footnote{However, one should remember that this theory does not provide any computational advantages. If it is hard to find the allocation that maximizes the sum of the utilities, then it is also hard  to find a Pareto optimal one (as they are the same in this case).}
\item The results of Bikhchandani and Mamer were extended to markets that  include production and uncertainty by Ygge~\citeyear[Chapter~3]{Ygge:98Thesis}. The relations between these types of markets and traditional optimization problems were also made more explicit in the latter work. 
\end{itemize}

Markets approaches have been applied to a number of different computerized applications, and some of them are briefly discussed here. Already in 1968 Sutherland proposed an auction mechanism for allocation of computational resources on a PDP-1 computer~\cite{Sutherland:68Futures}. Different amounts of money were assigned to different users in accordance with the importance of their projects. It was reported that the users then over time learn how to bid properly for computational resources. This basic approach has been further refined by, for example, Gagliano et al.~\shortcite{Gagliano:95}.

Kurose \& Simha~\citeyear{Kurose:89a} investigate a file allocation problem. In this work the agents report their marginal utility (for having a certain amount of storage) and its derivative to an auctioneer, which reallocates the resource using a resource-oriented Newton-Raphson algorithm~\cite<cf.\ >{Ygge:98ICMAS} until an equilibrium has been reached in which the marginal utilities of all agents are the same. Although the paper is based on a number of microeconomic abstractions, it does not for example utilize prices and there is no trade-off between different commodities. So, it is debatable whether this approach can be referred to as really market-based.\footnote{One should also note that the formulation of the Newton-Raphson scheme of this approach is overly simplistic, and there are much better standard methods available~\shortcite{Press:94a,Ygge:98ICMAS}.}

The assigning problem of allocating $n$ objects to $n$ users has been investigated by Bertsekas~\citeyear{Bertsekas:92Auction}. Each user has a valuation of each object, and cannot be assigned more than one object. It is reported that each user can be seen as an economic agent, and it is shown how an auction (which essentially is an English auction) results in an equilibrium. The assumed agent behavior is that an agent bids $v-w$ for its most highly valued object (i.e. the object with the highest difference, $v$, between the valuation and the price). $w$ is the difference between the valuation and the price of the second most preferred object. There is however no motivation given for the assumed agent behavior, and it is not clear why any agent would use this strategy unless it can be externally imposed. Though there is some economical interpretation of the prices, the approach is not very market-like due to the rather unrealistic assumptions of agent behavior.

The equilibria in the applications by Kurose and Simha, and Bertsekas are proven to be optimal. It is not hard to see that the problem of Kurose and Simha can be reformulated as a proper market with quasi-linear utility functions, and that the competitive equilibrium then is equivalent to the equilibrium described by Kurose and Simha, cf.~\cite[Corollary~3.3.1]{Ygge:98Thesis}. Similarly, the price vector obtained by Bertsekas clearly constitutes a competitive equilibrium. At the same time, it is shown by Ygge~\cite[Theorem~3.2]{Ygge:98Thesis}, that all separable optimization problems can be formulated in market terms and the (competitive) general equilibrium (if existing) is identical to the optimal solution to the original optimization problem. Consequently, this recent theory generalizes the earlier theory by for example Kurose and Simha, and Bertsekas.

Wellman et al.\ have contributed significantly in developing market-based approaches to resource allocation into a programming paradigm, which they have given the name \emph{market-oriented programming}, e.g.~\cite{Wellman:93a,Mullen:95a,Wellman:95a,Wellman:96a,Yamaki:96a,Hu:96a,Cheng:98a,Wellman:98Conjectural,Walsh:98ICDCS}. Particularly, the micro-economic framework of general equilibrium theory has been successfully used as a resource allocation mechanism. In such a market which we call an \emph{equilibrium market} agents send \emph{demand functions} telling how much they like to consume or produce at different prices. The auctioneer then tries to establish an equilibrium price vector such that supply meets demand for all commodities, cf. Figure~\ref{fig:inter}.


\begin{figure}
\begin{picture}(200,100)(-20,0)
\put(90,90){\makebox(0,0){Auctioneer}}
\put(50,60){\framebox(80,15){Initiate Auction}}
\put(130,67){\vector(2,-1){40}}
\put(40,20){\framebox(100,15){Supply = Demand?}}
\put(90,20){\vector(4,-1){60}}
\put(90,10){\makebox(0,0){Yes}}
\put(140,27){\vector(3,1){39}}
\put(160,25){\makebox(0,0){No}}
\put(210,90){\makebox(0,0){Trading Agent}}
\put(170,40){\framebox(80,15){Express demand}}
\put(170,47){\vector(-2,-1){30}}
\put(150,0){\framebox(120,15){Register and implement}}
\end{picture}
\caption{\it High-level view of an equilibrium market mechanism.}
\label{fig:inter}
\end{figure}

The process of submitting parts of the demand function may be iterated if an equilibrium price is outside the region captured by the submitted demand functions. One such process is the basic price t\^{a}tonnement process, cf. e.g.~\cite{Cheng:98a}, in which demand functions for the respective commodities are sent to an auctioneer. Each of those demands is based on {\em expected prices} of the other commodities. That is, if those other prices change, a set of new demand functions may need to be submitted. Once the auctioneer has established an equilibrium price, the agents will exchange the resources as stated by their bid and the equilibrium price. (For example, if an agent states that it wants to buy $1/p$ units of a commodity---where $p$ is the price in the commodity money---and the equilibrium price becomes $1$, the agent will buy one unit of resource for one unit of money.)

Equilibrium markets have many attractive theoretical properties. For example, if all agents act competitively\footnote{An agent that acts competitively treats prices as exogenous, that is, the impact on the prices due to its own behavior is negligible~\cite[p.~516]{Varian:96a}. This is a very reasonable assumption if the market is of at least moderate size and/or if there is uncertainty about the behavior of the other agents~\cite{Sandholm:97IJCAI}.}, the outcome is Pareto efficient. Furthermore, if all utility functions are quasi-linear, the outcome is globally optimal~\cite[Theorem~3.2]{Ygge:98Thesis}, and in the presence of uncertainty, the outcome maximizes the expected global utility~\cite[Theorem~3.5]{Ygge:98Thesis}. We note that equilibrium markets be computationally implemented in a computationally very efficient manner~\cite[Chapter~4]{Ygge:98Thesis}.

Wellman et al.\ have applied equilibrium markets to a number of applications, such as multi-commodity flow problems, design problems, and bandwidth allocation problems. They have also introduced a market-based approach to scheduling which has many similarities with the assignment problem of Bertsekas described above, but relies on more realistic assumptions on agent behavior. 

The present authors have introduced a market-oriented approach to power load management~\shortcite{Ygge:96a,Ygge:98Thesis,Ygge:99PAAM}. 

We note that the aim of market-oriented programming in computer science is fundamentally different from the aim of economic theory. This is visualized in Figure~\ref{fig:met}. In market-oriented programming, microeconomic theory is taken as given and serves as the theory for implementation of computational agents. Whether or not the microeconomic theory actually reflects human behavior is not the critical issue. The important question is instead how microeconomic theory can be utilized for the implementation of successful resource allocation mechanisms in computer systems. 
For example, even though no (or at least very few) people believe that humans use explicit utility functions when making their decisions, such functions do appear very useful to concisely represent human preferences for use in computational agents.

\postscript{14cm}{met}{\small \em A simplified view on the relation between economics and computer science with respect to microeconomic theory. Economists study humans and generate theory that is used for the explanation of human economic behavior. Computer scientists doing market-oriented programming use this theory as a basis for building working computational market systems.}

It is obviously very interesting to investigate the use of computational markets for automating trades between different self-interested parties, where information is private and is revealed only if there is an expected gain from doing so. However, the use of markets has also been proposed for standard resource allocation where the true utility/costs for all nodes that consume and produce resource is assumed to be available (though possibly uncertain and/or distributed in the system). The main arguments found in the literature for applying market to these types of problems are:
\begin{itemize}
\item The numerous similarities between economic systems and distributed computer systems suggest that models and methods previously developed within the field of mathematical economics can serve as \emph{blueprints} for engineering similar mechanisms in distributed computer systems~\cite{Kurose:89a}.
\item Auction algorithms are highly intuitive and easy to understand; they can be explained in terms of economic competition concepts, which are couched on everyday experience~\cite{Bertsekas:92Auction}.
\item Market approaches enable a natural decomposition, both from a software engineering perspective as well as from a computational perspective~\shortcite<>[Chapter~15]{Schreiber:99MIT,Ygge:98Thesis}.
\item Market approaches are very flexible in that they allow for ongoing addition and deletion of agents. No global changes are required---merely the demand/supply relation is altered~\cite[Chapter~15]{Ygge:98Thesis}.
\item Markets are informationally efficient in terms of information dimensionality~\cite{Jordan:82}, and the abstractions used are the most natural ones for the user~\cite[Chapter~15]{Ygge:98Thesis}.
\item The introduction of trading resources for some sort of money enables evaluation of local performance and valuation of resources, so that it becomes apparent which resources are the most valuable and which  agents are using the most of these~\cite[Chapter~15]{Ygge:98Thesis}.  
\end{itemize}

The above arguments are mainly conceptual and related to software/system design and engineering issues, and must prove their value from acceptance by software and system designers. But there are also different and in some respects stronger claims. For example, Huberman and Clearwater state~\cite{Huberman:95a} for the application of building control that: \emph{"While in principle an omniscient central controller with access to all the environmental and thermal parameters of a building (i.e. a perfect model) could optimally control it, in practice such knowledge is seldom available to the system. Instead, partial information about local changes in the variables (such as instantaneous office occupancy, external temperature, and computer use) is the only reliable source that can be used for controlling the building."} As an alternative to such an omniscient controller Huberman and Clearwater propose a market-based multi-agent approach to this problem.  This raises a very interesting question: Are there applications in which the information structure is such that market-based approaches do better than traditional approaches? In this paper we will carefully examine this issue for a building climate control problem. We will investigate what information different alternatives (traditional and new market-based) require, and what the performance of these different approaches are. We will use exactly the same problem formulation as Huberman and Clearwater in order to reproduce their results and evaluate other new approaches with their original formulation. This problem formulation is given in the next section.

\section{Problem Definition}
\label{sec:problemDef}
The task is to allocate a resource (cold air) in an office building, given the setpoint temperatures of the respective offices. As a measure of the success of the allocation, the standard deviation of the deviation from the setpoint is used~\cite{Huberman:95a}, i.e.
 \begin{equation}
   StdDev(T_i-T^{setp}) = \sqrt{\frac{1}{N}\sum_{o=1}^{N}
                        [(T_{io}-T_{o}^{setp})-(\langle T_{i}\rangle -
                        \langle T^{setp}\rangle)]^{2}}  ,
\label{eq:stddev}
\end{equation}
where $\langle \cdot \rangle$ denotes the average value of a variable, $T_{io}$ is the actual temperature of an office, and $T^{setp}_{o}$ is the setpoint temperature. The index $i$ denotes a time interval under observation and the index $o$ denotes the office under observation. This naming convention is used throughout the article. (In addition the index $k$ will also be used to denote time periods.)

It may be debated whether or not this is the best measure, but we stick to it in this article in order to evaluate the approach taken by Huberman and Clearwater using their own measure. 

\section{The Office Environment}
\label{sec:office}

The case study we consider for the comparison of decentralized markets versus central control solutions is the building climate control of a large office environment.

In this section, we present a mathematical-physical model of the
office environment. We first give a conceptual summary so that it is possible to understand the basic ideas of the model without studying the equations. The offices are attached to a pipe in which the
resource (cold air) is transported as in Figure~\ref{fig:offenv}. The
characteristics of this system are similar to the characteristics of a
district heating system, but with offices instead of households. We
assume that there are 100 offices in total, and that they are equally
distributed towards East, South, West, and North.

\postscript{14cm}{offenv}{\small \em Offices and air transportation.}

The thermodynamics of the office environment is actually quite simple.
Every office is seen as a storage place for heat, but heat may
dissipate to its environment. In the model, the thermodynamic
behavior of an office is equivalent to a basic electrical
RC-circuit. Here, voltage is analogous to temperature, and electrical
current is analogous to heat flow. $C$ and $R$ then respectively
denote heat capacitance and thermal resistance. 

A good general reference on thermodynamic models as the one we use here is the book by Incropera~\& Witt~\citeyear{Incropera:90a}. The heat equations are continuous in time, but
are discretized according to standard procedures from control
engineering, cf.~\cite{Ogata:90a}. The ontology and reusability
aspects involved in thermodynamics model construction are
discussed extensively by Borst, Akkermans,~\& Top~\citeyear{Borst:97a}.

\subsection{Thermodynamic Properties}

The resource treated is cooling power. Each office can make use only 
of a fraction, $\eta$, of the available resource at that office,
$P^{avail}_{io}$, so that 
\begin{equation}
       P^{cons}_{io} \leq \eta\cdot P^{avail}_{io},
\label{eq:limit}
\end{equation}
where $P^{cons}_{io}$ is the consumed power. The available resource at one
office is equal to the available resource at the previous office minus
the consumed resource at the previous office. Throughout this article we
assume an $\eta$ of 0.5. 

We treat everything in discrete time. The time interval we use in the calculations is one
minute. For all offices the temperature, $T_{io}$, is obtained by integrating a differential equation in discretized form:
\begin{equation}
   T_{io} = T_{0,o} + \sum_{k=1}^{i}(P^{heat}_{ko}-            P^{cons}_{ko})/C_{o},
\label{eq:maintemp}
\end{equation}
where $P^{heat}_{ko}$ is the heating power and $C_{o}$ is the thermal
capacitance. The heating power is described by
\begin{equation}
   P^{heat}_{io} = (T^{virt}_{io}-T_{io})/R_{o},
\label{eq:tempflow}
\end{equation}
where $R_{o}$ is the thermal resistance and $T^{virt}_{io}$ is a virtual
outdoor temperature, described in more detail below.

>From Eqs.~(\ref{eq:maintemp}) and (\ref{eq:tempflow}) we see that there is a feedback loop between the office temperature and the  heating power. Solving for the temperature we obtain
\begin{equation}
   T_{io} = \frac{1}{1+\frac{1}{R_{o}C_{o}}}\left(T_{i-1,o}
            + \frac{\frac{T^{virt}_{io}}{R_{o}}-              P^{cons}_{io}}{C_{o}}\right), \, i>0.
\label{eq:closedtemp}
\end{equation}
This is the equation for the dynamics of the system that can be directly computed. At the right-hand side we have known quantities, where $C_{o}$ and $R_{o}$ are externally given building parameters, $P^{cons}_{io}$ is the output of the utilized controller (as will be described in detail later in the article for various different controllers), and $T^{virt}_{io}$ is obtained from the weather model below.


\subsection{Weather Model}

All external weather influences on the office environment are modeled
by a virtual temperature, representing the outdoor temperature, sun
radiation, etc. We assume that there is sunshine every day and that the
outdoor temperature, $T^{outd}$, varies from $22$ to $35^\circ C$
according to
\begin{equation}
   T^{outd}_{i} = 22+13\cdot e^{-((i\cdot s-4) \, \,
                  mod \, \, 24 - 12)^2/20},
\label{eq:outdtemp}
\end{equation}
where $s$ is the length of each time interval expressed in hours, so 
here $s=1/60$.

The virtual temperature, $T^{virt}_{io}$, is described by
\begin{equation}
   T^{virt}_{io} = T^{outd}_{i}+T^{sun}_{o}+T^{fluct}_{io},
\label{eq:vtemp}
\end{equation}
where $T^{fluct}$ is a random disturbance, thought to represent small
fluctuations caused by for example the wind. $T^{fluct}$ is Gaussian distributed
with zero mean and a standard deviation equal to unity. $T^{sun}$ is the 
sun radiation component. For the offices located at the East side
$T^{sun}$ is described by
\begin{equation}
   T_{i}^{sun, East} = 8\cdot e^{-((i\cdot s+4) \, \,
                   mod \, \, 24 - 12)^2/5},
\label{eq:sunrade}
\end{equation}
and correspondingly for the South and the West offices
\begin{equation}
   T_{i}^{sun, South} = 15\cdot e^{-(i\cdot s \, \,
                    mod \, \, 24 - 12)^2/5} ,
\label{eq:sunrads}
\end{equation}
and
\begin{equation}
   T_{i}^{sun, West} = 8\cdot e^{-((i\cdot s-4) \, \,
                   mod \, \, 24 - 12)^2/5}.
\label{eq:sunradw}
\end{equation}

The various temperatures are plotted in Figure~\ref{fig:outdtemp}.

\postscript{16cm}{outdtemp}
{\small \em The plot at the left shows the outdoor temperature,
$T^{outd}_{i}$. The middle plot shows the sun radiation components,
$T^{sun}$, (with peaks at time 8, 12, and 16 hours for offices located
at the East, South, and West sides, respectively). Finally, the outdoor
temperature plus the sun radiation components are plotted at the
right.}

\subsection{Office Temperatures without Control}

In Figure~\ref{fig:rsandcs}, the temperature for a South-oriented
office is plotted with different thermal resistances, $R_{o}$, and
thermal capacitances, $C_{o}$. For simplicity we assume all $R_{o}$ to
be equal and all $C_{o}$ to be equal. From this figure we observe two
things: first, the higher $R_{o}C_{o}$ the bigger the lag in
temperature changes, and second, the higher $R_{o}C_{o}$ the smaller
the fluctuations in temperature. For the simulation experiments in this article we
took $R_{o}=10$ and $C_{o}=10$. An $R_{o}$ or a $C_{o}$ equal to zero
implies that $T_{io}=T^{virt}_{io}$, as can be seen by letting $R_{o}$ or
$C_{o}$ approach zero in Eq.~(\ref{eq:closedtemp}). Clearly, without control the office temperatures strongly fluctuate and reach unacceptably high values in all cases.

\postscript{14cm}{rsandcs}
{\small \em The indoor temperature for an uncontrolled office is
plotted for different values of the thermal resistance and the heat 
capacitance. Small values of the thermal resistance and capacitance
give higher peaks, while higher values give smoother curves.}


\section{{\sc Control-A}: Conventional Independent Controllers}
\label{sec:controlA}

\subsection{Integral Control for the Offices}

The application of regulating office temperature has a long
tradition in control theory. The most widely known controllers are
different variants of the PID controller. The letters PID denote that
the control signal is proportional (P) to the error (that is, to the difference
between the setpoint and the actual value);
proportional to the integral (I) of the error; or proportional
to the derivative (D) of the error. Here, we use a variant
of an integrating controller\footnote{The main reason for choosing an integrating controller is that we want to have a setting that is as close as possible to the setting described by Huberman and Clearwater~\citeyear{Huberman:95a}. Other controllers for this application may well be considered, but as long as the performance is as good as shown in Figure~\ref{fig:contr}, this is not at all crucial for the central argument of this article.} 
of the form
\begin{equation}
   F_{io} = F_{i-1,o} + \beta(T_{io}-T^{setp}_{o}),
\label{eq:controller}
\end{equation}
where $F$ is the output signal from the controller, and $\beta$ is a
so-called gain parameter (that can be set externally in the design of the controller). For the simulations it is assumed that $F_{io}$ is
limited to a value between zero and three. This is in order to model that the valves can be closed but that cooling resources are not delivered from one room to another (the lower bound), and that there is a maximum to the amount of resources that can be obtained by opening the valve fully (the upper bound). The control signal
$F_{io}$ is sent to the actuator and the actual $P^{cons}_{io}$ is obtained from
\begin{equation}
   P^{cons}_{io} =  
   \left\{ \begin{array}{ll}
   F_{io}, & F_{io} \leq \eta\cdot P^{avail}_{io} \\ 
   \eta\cdot P^{avail}_{io}, & F_{io} > \eta\cdot P^{avail}_{io}       \end{array}\right..
\label{eq:contrToPower}
\end{equation}

Plots of the office temperatures with different gains are shown in
Figure~\ref{fig:contr}. The gain of the controller is not critical for
this application. Too high a gain will result in the controller
overreacting when the temperature exceeds the setpoint, after which it
will be under the setpoint for quite some time. This leads to a larger
error than if smaller adjustments are made. Also, the amplitude of the
control signal then gets unnecessarily high, but the system does not
get dangerously unstable. We note that the maximum deviation here is
$\pm 0.06^\circ C$. Thus, controllers using any of the three gains
perform very well. In the further calculations of this article a gain equal to 10 has been adopted. 

\postscript{14cm}{contr}
{\small \em The indoor temperature for an office, utilizing an
integral controller, is plotted for different controller gains.
The setpoint temperature is $20^{\circ} C$.}

\subsection{The Implications of Limited Resources}

So far, we have assumed that the total amount of available resources is 
unlimited. Now, we suppose that there is a maximum value for the cooling power
that is inserted into the system. In such a situation, offices that are
situated close to the air input will obtain a sufficient amount of cool
air, but those near the end will suffer if totally uncoordinated
controllers are used. Thus, the smaller the total amount of available resources, the larger the standard deviation will be. This is
visualized in Figure~\ref{fig:hund}. As a reasonable figure we have chosen an
upper limit for the total resource amount of $140$.

\postscript{16cm}{hund}
{\small \em The standard deviation (in ${}^\circ C$) , as defined in
Eq.~(\ref{eq:stddev}) for each interval, $i$, is plotted for different
amounts of available cold air resources (130, 140, 150, and 160) with 100
offices. The lower the amount of available resources, the higher the
standard deviation.}

We conclude, as shown by the example, that independent integrating controllers perform
very well when the amount of cooling resources is unlimited. On the other hand, when
there is a shortage of available resources, the standard deviation increases
dramatically, yielding poor performance.

\section{{\sc Market-A}: The Approach by Huberman and Clearwater}
\label{sec:marketA}

A multi-agent systems solution to the problem of building control has been presented
by Huberman and Clearwater \citeyear{Clearwater:94a,Huberman:95a}. The
approach taken is to model the resource allocation problem of the
building environment as a computational market where agents buy and
sell cooling power resources. The non-separability in terms of agents is ignored.\footnote{A resource allocation problem is separable if the total utility of the system of the system can be expressed as the sum of the utilities of each node (producer/consumer), and the only constraints on how much resource that can be assigned to each node is only restricted by that their sum must not exceed the total available resource~\cite{Ibaraki:88a}. Hence, the problem treated in this paper is not separable as there are other constraints on how the resource can be distributed. For example, if we assign sufficiently much to the penultimate agent, the ultimate will have a significant amount of resource available.} 

The basic idea is that every office is represented by an agent that is
responsible for making good use of its resources, and to this end trades
resources with other agents. The agents send bids to
an auctioneer, which calculates a clearing price, and makes sure that no
agent has to buy for a price higher than its bid nor has to sell for a
price lower than its bid.

In this section we give the market protocol proposed by Huberman and Clearwater, and we reproduce their results. In order to make the paper self-contained, the interested reader can find the original equations underlying the Huberman-Clearwater market protocol in Appendix~\ref{sec:orgform}.

\subsection{Market protocol}
A bid is constructed as the following tuple:
\begin{equation}
   bid = [ sell_{io}, v_{io}, B_{io} ],
\label{eq:bidTuple}
\end{equation}
where $sell$ is a boolean variable indicating whether the current bid is a $sell$ bid ($true$) or buy bid ($false$), $v$ is the volume traded for, and $B$ is the price that the agent demands (sell bid) or is prepared to pay (buy bid). 

Each of the variables in Eq.~(\ref{eq:bidTuple}) is a  function of other variables according to
\begin{equation}
\begin{array}{ll}
    sell_{io} = sell_{io}(T_{io},T_{o}^{setp}, 
                            \langle T_{i} \rangle, \langle T_{o}^{setp} \rangle), \\
    v_{io} = v_{io}({\mathbf T}_i,{\mathbf T}^{setp},\alpha), \mbox{and}\\
    B_{io} = B_{io}(T_{io},T_{o}^{setp}, 
                            \langle T_{i} \rangle, \langle T_{o}^{setp} \rangle, m_{io}),
\end{array}
\label{eq:dependencies}
\end{equation}
where ${\mathbf T}_i = [T_{i1}, T_{i2}, \ldots , T_{i100}]$, ${\mathbf T}^{setp}= [T_1^{setp}, T_2^{setp}, \ldots , T_{100}^{setp}]$, $\alpha$ is a strength parameter of the auction, and $m_{io}$ is called a money parameter. The trade volume is directly proportional to $\alpha$ and, hence, doubling $\alpha$ doubles the traded volume in an auction. Thus, $\alpha$ is a free parameter that can be externally set to tune the trade volumes to proper levels. The money parameter does not correspond to any real currency; it is merely a control variable, varying between $100$ and $200$, and it does not have any direct connection to, for example, the value of the cooling resource. The money cannot be saved between auction rounds in the Huberman-Clearwater protocol, another indication that it simply functions as an adjustment parameter in this protocol.

An auction consists of the following three phases:
\begin{enumerate}
\item All agents send their bids, $[ sell_{io}(T_{io},T_{o}^{setp}, 
                            \langle T_{i} \rangle, \langle T_{o}^{setp} \rangle$, 
                            $v_{io}({\mathbf T}_i,{\mathbf T}^{setp},\alpha)$,
                            $B_{io}(T_{io},T_{o}^{setp}, 
                            \langle T_{i} \rangle, \langle T_{o}^{setp} \rangle, m_{io}) ]$, to the auctioneer.

\item The auctioneer then computes a market clearing price by searching for the following minimum: 
\begin{equation}
\min_{p_i} \left| \sum_{o|sell=true, B_{io} \leq p_i} v_{io} - \sum_{o|sell=false, B_{io} \geq p_i} v_{io} \right| .
\label{eq:compEqPrice}
\end{equation}
This yields a price such that supply matches demand as closely as possible.

\item Finally, the resources are allocated as dictated by the above bids and the obtained market price, according to the rule: all sellers that are offering $v_{io}$ for a price, $B_{io}$, that is lower than or equal to the market price will sell $v_{io}$; and correspondingly for buyers.\footnote{Since the bids are given using discrete volumes, supply will seldomly
match demand \emph{exactly} at the clearing price. Normally, there
will be a very small excess demand or supply. If there is an excess
supply, all buyers that are willing to pay at most the clearing price
will buy, but not all sellers that are willing to accept at least the
clearing price can sell. In this situation, a seller is selected
randomly from the valid candidates does deliver only a fraction of its bid. A corresponding procedure is used when
there is a small excess demand.}
\end{enumerate}

As an example of the computation of the equilibrium price, assume that the auctioneer has received the following bids $[true,2,4]$, $[true,1,3]$, $[true,2,2]$, $[false,1,3]$, $[false,2,2]$, $[false,2,1]$. Then the market clearing price is $3$, leading to acceptance of bid $2, 3, 4,$ and $5$. (Bid $1$ is too high a sell price and bid $6$ is too low a buy price.)

\subsection{Simulations}
\label{sec:simulations}

Figure~\ref{fig:orgsim} shows two plots of a simulation for the period between 3 p.m.\ and 7 p.m.\footnote{All solutions discussed in this article have been implemented in and simulated by the authors using C++ on a PC running Windows95. Furthermore, all simulations have been independently recreated and verified by Bengt Johannesson from various relevant papers~\cite{Ygge:97MAAMAW,Huberman:95a,Clearwater:94a}), as part of a master's thesis project, using Python on a PC running Linux.} The initial temperatures for all offices were set to $20^\circ C$. The upper plot is the
standard deviation when independent integrating controllers are used,
and the lower one shows the agent-based control scheme as defined
above. We found that for the adjustment parameter $\alpha$ (see Eq.~(\ref{eq:rel_vol})) a value of $64$ led to the smallest overall standard
deviation. The key observation from the figure is that the agent approach offers at least one
order of magnitude of improvement.

\postscript{15cm}{orgsim}{\small \em Standard deviation for
independent controllers (top) and agent-based control (bottom).}

Compared to independent conventional controllers this is indeed a major
advance, and this is the central claim made by Huberman and Clearwater. The market approach given above leads to a reduced control error and thus to increased comfort compared to standard controllers. Our simulations thus reproduce and validate the results of Huberman \& Clearwater~\citeyear{Clearwater:94a,Huberman:95a}.

However, this cannot be the last word in a successful system study. A first question to be raised is whether we can find out in more detail what the actual reason is for the success of the above market-based approach. A second relevant question is whether there are alternative, market-based and/or central control-based, solutions to the building control problem that are even better. The answer to both questions is \emph{yes}, as we set out to demonstrate now.

\section{{\sc Market-A}$'$: A Suite of Variations}
\label{sec:marketAP}

In this section we present a suite of variations on the scheme
presented in Section~\ref{sec:marketA}. The main aim is to understand which of many factors involved are actually responsible for the good performance of the Huberman-Clearwater market approach. 

\subsection{Deleting the Money Dependency}
A first simplification is to remove the adjustment parameter called money. This is done by setting $m_{io}$ to a very high value, $C$, regardless of the resource allocation.\footnote{More precisely, this is done by setting $U(0,m)$ in Eq.~(\ref{eq:U0}) (Appendix~\ref{sec:orgform}) to a constant value, $2000$. This corresponds to letting $m_{io}$ approach infinity.} 
The simplified market protocol then is: 

\begin{enumerate}

\item All agents send their bids, $[ sell_{io}(T_{io},T_{o}^{setp}, 
                            \langle T_{i} \rangle, \langle T_{o}^{setp} \rangle$, 
                            $v_{io}({\mathbf T}_i,{\mathbf T}^{setp},\alpha)$,
                            $B_{io}(T_{io},T_{o}^{setp}, 
                            \langle T_{i} \rangle, \langle T_{o}^{setp} \rangle, m_{io} = C) ]$, to the auctioneer.

\item The auctioneer computes a market price from
\begin{equation}
\min_{p_i} \left| \sum_{o|sell=true, B_{io} \leq p_i} v_{io} - \sum_{o|sell=false, B_{io} \geq p_i} v_{io} \right|.
\end{equation}

\item Allocate the resource as dictated by the bids and the market clearing price.
\end{enumerate}

\postscript{15cm}{nomoney}{\small \em Standard deviation for the
original Huberman-Clearwater scheme and a scheme without any money dependencies.}

Plots of the standard deviation with the original scheme as well as
with a scheme where all money dependencies have been removed are shown in Figure~\ref{fig:nomoney}. For the scheme without money, setting the  $\alpha$
parameter to $66$ turned out to be optimal.
The scheme without money dependencies performs as well as the original scheme.
The reason for this is that $B_{io}$'s dependency on $m_{io}$ is completely negligible.\footnote{In actual fact, $U(0,m)$ in Eq.~(\ref{eq:U0}) of Appendix~\ref{sec:orgform} will vary only between $1999.86$ and $2000$ for all possible $m_{io}$.}
Hence, the money parameter does not play any significant role in the 
success of the Huberman-Clearwater market scheme.

\subsection{Deleting the Temperature Dependency}
Another factor of interest is the impact of the temperature on the bid prices. We remove this dependency by setting the bid price to $10$ for all selling agents and to $100$ for all buying agents. That is, we now use the following market scheme:

\begin{enumerate}

\item All agents send their bids, \\ 
$[ sell_{io}(T_{io},T_{o}^{setp}, 
                            \langle T_{i} \rangle, \langle T_{o}^{setp} \rangle)$, 
                            $v_{io}({\mathbf T}_i,{\mathbf T}^{setp},\alpha)$,
                            $B_{io} = \left\{\begin{array}{ll} 10, &sell=true \\ 100, &sell=false\end{array} \right. ]$, \\ 
to the auctioneer.

\item Now, all prices larger than $10$ and smaller than $100$ are equally good candidates. If there is a mismatch between supply and demand, say, supply exceeds demand, the agents that will sell are picked randomly among the valid candidates, and the resources are allocated accordingly.
\end{enumerate}

\postscript{15cm}{notemp}{\small \em Standard deviation for the scheme
with the money dependencies removed, compared to a scheme with both the
money and temperature dependencies removed.}

In Figure~\ref{fig:notemp} the standard
deviation is plotted for the scheme without money, mentioned above, and for 
a scheme where the dependency on the temperature has been removed as
well. Here, setting the fit parameter $\alpha$ to $65$ turned out to be
optimal. We see that also here the performance is as good as that of the original scheme. Note that the temperature is still used to determine both $v_{io}$ and the boolean variable $sell$. But the conclusion is that the temperature dependency does not affect the 
quality of the market-based solution to the building control problem. 

\subsection{Deleting the Auction}
Next, we let the agents assign their bids to themselves {\em without any
auction whatsoever}. This means that the sum total of the controller
outputs, $F_{io}$, might sometimes exceed the total resource amount
and sometimes be below that. The physical model is of course still obeyed,
so that the total resource amount actually used, the total consumed cooling
power $P^{cons}_{io}$, will never exceed the totally available
resource amount, as described by Eq.~(\ref{eq:limit}). Hence, the resource updates are described by:
\begin{equation}
\begin{array}{ll}
    F'_{io} = F_{i-1,o} \left\{ \begin{array}{ll} +v_{io}({\mathbf T}_i,{\mathbf T}^{setp},\alpha), &sell=false \\ -v_{io}({\mathbf T}_i,{\mathbf T}^{setp},\alpha), &sell=true \end{array} \right. \\
     F_{io} = \left\{\begin{array}{ll} 0, &F'_{io}<0 \\ F'_{io}, &0 \leq F'_{io} \leq 3 \\ 3, &F'_{io}>3 \end{array} \right.
\end{array}
\label{eq:noAuction}
\end{equation}

\postscript{15cm}{nocoord}{\small \em Standard deviation with the
auction mechanisms completely removed, compared to the original Huberman-Clearwater \mbox{\textsc{Market-A}}
scheme.}

The result of this
simulation is shown in Figure~\ref{fig:nocoord}. Here, an
$\alpha$ of $17$ turned out to be optimal. The surprising conclusion is that the multi-agent scheme {\em without} performing any auction  
is roughly ten times better than the 
auction-based \mbox{\textsc{Market-A}} scheme.\footnote{From a practical point of view this is a pathological solution, revealing a loophole in the problem definition of Clearwater and Huberman, cf.~Section~\ref{sec:problemDef}. The revealed loophole of the problem definition is that it does not take absolute temperature into account, but only the differences between temperature (i.e. minimizing standard deviation while potentially sacrificing average temperature). In the proper approaches introduced in the remainder of this article we do not allow ourselves to take advantage of this loophole, but minimize differences while using all available resource. That is, all approaches that are introduced from now on solve a problem which is strictly harder than the problem defined in~Section\ref{sec:problemDef}.  
What happens in the {\textsc Market-A} scheme without an auction can be seen from observing the definition of $t_{io}$ in Eq.~(\ref{eq:tradeVol}). It is based on a quotient between the setpoint temperature and the actual temperature. Then the request volume, Eq.~(\ref{eq:deltaVAV}), is proportional to this quotient. This always results in a significant excess supply. (Hint, think of a small example with two offices, both with setpoint $20$, and with temperatures $19$ and $21$. Now, $\frac{20}{19}$ is farther away from $1$ than $\frac{20}{21}$, and hence the selling volume will exceed the buying volume.) This implies that at each trade occasion, many offices are prevented from selling (because of poor definitions of the volumes). The offices that are prevented to sell will deviate significantly, and hence this results in a high value of the measure. When the auction is deleted, all agents that are below the average distance to the setpoints are now able to get rid of the resource and hence the differences in temperature will decrease.
}


\subsection{Discussion}
At first glance, it might seem counterintuitive that performance
actually \emph{improves} significantly when the core
mechanisms of a market are removed. First we showed that introducing
the market improves performance considerably compared to conventional independent control, and then we showed that market mechanisms are superfluous. What, then, is the big
difference between the uncoordinated integrating controller, the
\mbox{\textsc{Control-A}} scheme, and the multi-agent scheme without any auction that we
ended up with? The simple answer, in our view, is the \emph{access to
global data that each agent has}, in terms of the {\em average} temperature and the {\em average}
setpoint temperature (as follows from Eq.~(\ref{eq:dependencies})), in the \mbox{\textsc{Market-A}} and
\mbox{\textsc{Market-A}}$'$ schemes. Knowing average quantities means that an agent has some information about the {\em other} agents c.q. offices. This information is not available in the case of independent conventional controllers. The exploitation of this non-local information makes the big difference. 

Thus, the upshot of our factor analysis of the success of the Huberman-Clearwater market scheme of Section~\ref{sec:marketA} is that 
the agents have to share crucial office and control information first, before the auction takes place. This is why one can remove the auction without any deterioration of the results: a major function of an auction is to share necessary information through the bidding procedure, but in the Huberman-Clearwater protocol the needed information has already been shared. A more appropriate description of this market scheme would therefore be to say that it consists of not three (as described in Section~\ref{sec:marketA}), but four phases, in which the first phase is that all agents send their current temperatures $T_{io}$ as well as their setpoint temperatures $T_{o}^{setp}$ to all other agents.

In sum, we have now answered the first question raised at the end of the previous section: What is the reason for the success of the Huberman-Clearwater market scheme, compared to conventional independent controllers? The single most important factor is contained in the first step above: \emph{before} the market procedure is carried out, the agents communicate key information about their current situation to all other agents. If that is done neither money nor auction mechanisms are needed. For conventional independent controllers, with which Huberman and Clearwater compare their own approach, this globally shared information is \emph{not} available, however. This explains why these two solutions perform so very differently. 

Now, we turn to the second question raised in the previous section: are there alternative and perhaps better solutions? The above analysis suggests that we look into two different directions. If one wants to persuade control engineers of the value of agent-based approaches, 
it will be more convincing to compare the Huberman-Clearwater scheme not to strictly local controllers, but to controllers that have access to the same global information as the agents have. Secondly, this dependency on global information by the agents is a highly undesirable feature that clearly runs counter to a decentralized computational market philosophy. So, one should investigate whether it is possible to design a market protocol that exploits only strictly local information in the agents' bid construction. These issues we investigate in the following two sections, first treating central control and subsequently devising a strictly local market protocol. 
It will be seen that both yield significantly improved performance.


\section{\mbox{\textsc{Control-B}}: A Standard Controller Using Global Data}
\label{sec:controlB}

Having concluded that the access to global data is crucial for
performance, it is of course of interest to analyze what the
performance would be of an integrating controller, like the one introduced in
Eq.~(\ref{eq:controller}), \emph{but now incorporating global data}.

We would like the controller to take into account not only its own
deviation from its setpoint, but to consider also the deviations of
the other offices from their setpoints. Therefore, the controller in
Eq.~(\ref{eq:controller}) is extended to
\begin{equation}
   F_{io} = F_{i-1,o} + \beta[(T_{io}-T^{setp}_{o}) -
            (\langle T_{i}\rangle - \langle T^{setp}\rangle)] ,
\label{eq:avgcontr}
\end{equation}
where $\beta$ is set to 10 as previously. $P^{cons}_{io}$ is, as
before, obtained from Eq.~(\ref{eq:contrToPower}).

The plot from the simulation with this controller, compared to the
\mbox{\textsc{Market-A}} simulation, and to the \mbox{\textsc{Market-A}}$'$
simulation where the auction was removed, is shown in
Figure~\ref{fig:controlb}.

\postscript{15cm}{controlb}{\small \em Standard deviation with an
integrating controller that utilizes global data compared to the
Huberman-Clearwater \mbox{\textsc{Market-A}} scheme, and to the \mbox{\textsc{Market-A}}$'$ scheme with the
auction removed.}

We see that the standard deviation is approximately the same for the
\mbox{\textsc{Control-B}} and the \mbox{\textsc{Market-A}}$'$ schemes. Thus, the \mbox{\textsc{Control-B}} scheme also performs roughly ten times better than
\mbox{\textsc{Market-A}}. An important difference, though, is that {\sc
Control-B} employs a well-known integrating controller for which
there are well-understood methods and theories for e.g. stability
analysis.\footnote{This holds under the assumption that the characteristic time scale
of the variations of the average temperature is much larger than that of the
fluctuation of the temperature. This is a very reasonable assumption
in the present case.} In contrast, the {\sc Market-A} scheme
is not easily analyzable from a formal theory perspective, since it
does not rely on such well established concepts. While \mbox{\textsc{Control-B}} is relatively clear, see Eq.~(\ref{eq:avgcontr}), it is much harder to conceptually grasp the principles behind \mbox{\textsc{Market-A}}, as it consists of a large number of complicated and not easily justified equations (see Eqs.~(\ref{eq:buyorsell})--(\ref{eq:bid}) in Appendix~\ref{sec:orgform}). The main conclusion from the present section is that, if we enable conventional controllers to act upon the same global information as the Huberman-Clearwater agents do, the central control approach performs best and is easiest to understand. 

\section{{\sc Market-B}: A Market with Local Data Only}
\label{sec:marketB}

Thus, the computational market {\sc Market-A} is outperformed by the global control scheme
\mbox{\textsc{Control-B}}. Therefore, an interesting follow-up question is whether a simple and well
performing computational market approach can be devised that does {\em
not} depend on having available global information, in contrast to
both these schemes. In this section we show that this is indeed the
case, such that a decentralized market performs comparably to fully centralized conventional control. The approach derived in this section relies on more general theory for the relations between optimization problems and markets--\cite[Chapter~3]{Ygge:98Thesis} and \cite{Bikhchandani:97} -- applicable to this and many other applications.

We use a market-oriented programming approach based on an equilibrium market. The basic protocol for this is (cf. Figure~\ref{fig:inter}):

\begin{enumerate}
\item Each agent submits a \emph{net demand function} $z_{io}(p)$ to the auctioneer, describing what change in allocation is desired by agent $o$ at price $p$. 

\item The auctioneer computes an equilibrium, by calculating a price $p_i$ such that $\sum_o z_{io}(p_i) = 0$ (or, strictly speaking, $|\sum_o z_{io}(p_i)| \leq \epsilon$, where $\epsilon$ is a small (positive) numerical tolerance).
 
\item Each agent receives its demanded resource $z_{io}(p_i)$ as calculated at the obtained market equilibrium price.
\end{enumerate}

The computation of $z_{io}(p)$ and the process of computing the equilibrium are described further below. Note that this is a truly distributed approach, as it does not rely on any global data, or communication of temperatures between the agents before the market communication starts.

\subsection{The Relation Between Markets and Conventional Controllers
utilizing Global Data}

The performance measure for the system is given by
Eq.~(\ref{eq:stddev}). The best system is therefore one that
minimizes this equation. Hence, the most straightforward move one can
think of to come to a market model, is to take {\em this} measure as
representing the utility function for the overall system. So, the
utility functions for the individual agents are ideally
related to $[(T_{io}-T_{o}^{setp}) -
(\langle T_{i}\rangle - \langle T^{setp}\rangle)]^{2}$.~\footnote{Since utilities are expressions of preference orderings,
they are invariant under monotonic transformations.} However, this is
still a formulation containing global information.

Thus, we want to obtain a {\em purely local} reformulation, by getting
rid of the terms with $\langle T \rangle$ containing the global
information. We might replace them, though, by terms relating to the
changes in the local resource. In doing so, we take inspiration from
the standard controller equations Eqs.~(\ref{eq:controller}) and (\ref{eq:avgcontr}), indicating that we get good results (for
unconstrained resources) with the update equation $ F_{io} =
F_{i-1,o}+\phi_{io}$, when $\phi_{io}$ has the form $\phi_{io} = \beta
(T_{io}-T_{o}^{setp})$. The intended interpretation of $\phi_{io}$ is
to represent the output that the local controller would have delivered
if it acted independently with unconstrained resources. In the market
setting each agent updates its control signal $F_{io}$ through $F_{io}
= F_{i-1,o} + \Delta F_{io}$, where $\Delta F_{io}$ is determined by
the outcome of the market. Since the resource is only redistributed
among the agents, we have that $\sum_{o=1}^{N}{\Delta F_{io}} = 0$.
Accordingly, as a step in the design of a {\sc Market-B} scheme, based
on local data only, we employ the following definition.

\begin{definition}
Let the utility function for the individual
office agents be defined by
\begin{equation}
   u(\Delta F_{io},m) =
   -\alpha _{o}^{2}(\Delta F_{io} - \phi_{io})^{2}+m,
\label{eq:properUtility}
\end{equation}
where $\alpha_{o}$ is a strength parameter for each office
representing its physical properties such as $R_{o}$ and $C_{o}$. (The proper choice of $\alpha_{o}$ is discussed in Theorem~\ref{theor:optimal} later on.)

Furthermore, let all agents be price-takers.

\label{defi:properUtility}
\end{definition}

Due to the simple quadratic form of the utility function in Eq.~(\ref{eq:properUtility}), the net demand, $z_{io}(p)$, is easily computed for price-taking agents by analytical means. Note that the money $m$ here are fundamentally different from the money of {\sc Market-A}, c.f.\ Section~\ref{sec:marketA}. Here the money represents a commodity and the agent needs to decide how much money to trade for the commodity cold air. As described above, the money in Section~\ref{sec:marketA} is just a control variable without an intuitive interpretation.

\begin{theorem}
With the utility functions and behavior given by Definition~\ref{defi:properUtility}, there exists a unique equilibrium price $p_i|\sum_o z_{io}(p_i) = 0$, and the allocation obtained by the equilibrium market is Pareto optimal.
\label{theor:existence}
\end{theorem}

\proof{See~\cite{Mas-Colell:95a,Varian:92a,Takayama:85a}.} $\Box$ 

In this setting, there is a wide variety of different algorithms that are guaranteed to converge to the clearing price $p_i|\sum_o z_{io}(p_i) = 0$, in the second step of our equilibrium market protocol given above. Examples of such algorithms are price t\^{a}tonnement, \textsc{Walras}~\cite{Cheng:98a}, and various Newton-Raphson type methods. A detailed discussion of communication and  computation efficiency aspects of such algorithms is given by Ygge~\citeyear[Chapter~4]{Ygge:98Thesis}.

\begin{theorem} 
Any Pareto optimal outcome in a market in which the agents
hold the utility function of Eq.~(\ref{eq:properUtility}) \textbf{is
equivalent to} an integrating controller that exploits global information as described by the following resource update
equation :
\begin{equation}
   \Delta F_{io}=\phi_{io}-
         \frac{1}{\alpha_{o}^{2} \cdot \langle 1/ \alpha^{2} \rangle}
         \langle \phi_{i} \rangle ,
\label{eq:generalDeltaFn}
\end{equation}
given that no agent is at its boundary. Here, $\langle 1/ \alpha^{2} \rangle$ and $\langle \phi_{i} \rangle$ are the average $1/ \alpha_o^{2}$, and $\phi_{i0}$ respectively.
\label{theor:global}
\end{theorem}

\proof{
At a Pareto-optimal allocation where no agent is at its bounds, all $\partial u(\Delta F_{io})/\partial \Delta F_{io}$ are equal. (Assume $\partial u(\Delta F_{ip})/\partial \Delta F_{ip} < \partial u(\Delta F_{iq})/\partial \Delta F_{iq}$, then at any price $\partial u(\Delta F_{ip})/\partial \Delta F_{ip} < p < \partial u(\Delta F_{iq})/\partial \Delta F_{iq}$, there exists a (sufficiently small) amount of  $\Delta F_{i}$, say $\epsilon$, such that $u_p(\Delta F_{ip}- \epsilon, m_{ip} + p\epsilon) > u_p(\Delta F_{ip}, m_{ip})$ and $u_q(\Delta F_{iq}+ \epsilon, m_{iq} - p\epsilon) > u_q(\Delta F_{iq}, m_{iq})$. Correspondingly for $\partial u(\Delta F_{ip})/\partial \Delta F_{ip} > \partial u(\Delta F_{iq})/\partial \Delta F_{iq}$. Hence, $\partial u(\Delta F_{ip})/\partial \Delta F_{ip} = \partial u(\Delta F_{iq})/\partial \Delta F_{iq}$).

Thus, it will hold for every office that
$\Delta F_{io}-\phi_{io} = \frac{\alpha_{N}^{2}}{\alpha_{o}^{2}}
(\Delta F_{iN} - \phi_{iN})$.
Summing the equations yields
$\sum_{o=1}^{N-1}\Delta F_{io} - \sum_{o=1}^{N-1} \phi_{io} =
\alpha_{N}^{2} ( \Delta F_{iN} - \phi_{iN} )
\sum_{o=1}^{N-1}\frac{1}{\alpha_{o}^{2}}$. Adding $\Delta F_{iN} - \phi_{iN}$ to both sides and dividing both sides by $N$ together with the resource constraint ($\sum_{o=1}^{N}{\Delta F_{io}} = 0$)
yields $\frac{ - \sum_{o=1}^{N} \phi_{io}}{N} =
\alpha_{N}^{2} ( \Delta F_{iN} - \phi_{iN} )
\frac{\sum_{o=1}^{N}\frac{1}{\alpha_{o}^{2}}}{N}$ which is equivalent to $\Delta F_{iN} = \phi_{iN} -
\frac{1}{\alpha_{N}^{2} \cdot \langle 1/ \alpha^{2} \rangle}
\langle \phi_{i} \rangle $.
For reasons of symmetry, this equation holds for all offices.
$\Box$
}

\begin{corollary}
For the special case where all $\alpha_{o}$ are
equal, and $\phi_{io} = \beta (T_{io}-T_{o}^{setp})$,
Eq.~(\ref{eq:generalDeltaFn}) becomes exactly the
\mbox{\textsc{Control-B}} scheme captured by Eq.~(\ref{eq:avgcontr}).
\label{coro:globalSpec}
\end{corollary}

Consequently, it also follows that simulation results for an equilibrium \mbox{\textsc{Market-B}} scheme, based on the utility function of Eq.~(\ref{eq:properUtility}) with the provisions given in the above corollary, \emph{are identical} to those of the  centralized \mbox{\textsc{Control-B}} scheme, cf. Figure~\ref{fig:controlb}. This fully decentralized market scheme thus performs better than the original Huberman-Clearwater market protocol.

In sum, we see that (under suitable conditions which are fulfilled here) \emph{local data plus market communication is
equivalent to conventional central control utilizing global data}. Even though
our proof was based on the assumption that the agents are
never at their boundary values, it will be a close approximation
in many practical applications. It should also be noted that
managing the boundaries is not required for a successful
implementation. As seen above, omitting the management of boundaries
in the current application leads to \mbox{\textsc{Control-B}}, which was
shown to have a very high performance.

\subsection{Finding an Optimal Utility Function}

In this section we show how an optimal utility function is constructed
in the {\em constrained} case, from an optimal controller for the {\em
unconstrained} case.\footnote{The resource is constrained when the action of any agent is limited by $P_{io}$, see Eq.~(\ref{eq:contrToPower}) and Figure~\ref{fig:hund}. It is unconstrained when such a limitation is not present, cf. Figure~\ref{fig:contr}.} Earlier we noted that it is debatable whether or not the measure in Eq.~(\ref{eq:stddev}) is a good one. One argument against it is that it allows for pathological solutions, as it does not take the average indoor temperature into consideration. If we for example increase the indoor temperature in every office by $10^\circ C$, all of them could be unbearably hot, while the measure might be minimized. A reasonable thing to do here, to prevent these kind of solutions, is to treat the average temperature as given (the result of using all available resources). If we do so, the following theorem shows how an optimal utility function is constructed
in the constrained case, from an optimal controller for the unconstrained case. 

\begin{theorem}
If $T_{io}$ is a linear function of
$\Delta F_{io}$,\footnote{From the thermal model discussed in Section~\ref{sec:office}
(especially Eqs.~(\ref{eq:closedtemp}) and (\ref{eq:contrToPower})) we
note that this is indeed the case for a reasonably wide range.}
and if $\phi_{io}$ minimizes Eq.~(\ref{eq:stddev}) in the
unconstrained case, then in a market where the utility functions are
described by Eq.~(\ref{eq:properUtility}), with
$\alpha _{o}=\frac{\partial T_{io}}{\partial \Delta F_{io}}$,
any associated Pareto optimal allocation minimizes Eq.~(\ref{eq:stddev}) in
the constrained case, if the resource can be independently allocated
among the agents (i.e., when the only constraint on $\Delta F_{io}$ is the upper and lower bound, and $\sum_{o=1}^N \Delta F_{io}=0$), and the average temperature is considered as given. 
\label{theor:optimal}
\end{theorem}


\proof{
Minimizing Eq.~(\ref{eq:stddev}) boils down to minimizing
$f(T_{i1}, T_{i2}, \ldots\ ,T_{in}) =
\sum_{o=1}^{N}[(T_{io}-T_{o}^{setp}) -
(\langle T_{i}\rangle - \langle T^{setp}\rangle)]^{2}$,
since this is just a monotonic transformation. Due to the fact that 
$\phi_{io}$ minimizes Eq.~(\ref{eq:stddev}), it holds that
$\frac{\partial f}{\partial \Delta F_{io}} = 0$
for $\Delta F_{io} = \phi_{io}$. Since the average temperature is considered as given, we have that $\frac{\partial f}{\partial \Delta F_{io}} = 2[(T_{io}(\phi_{io}) - T_{o}^{setp}) -
(\langle T_{i}\rangle - \langle T^{setp}\rangle)] \cdot \frac{\partial T_{io}}{\partial \phi_{io}}$ for $\Delta F_{io} = \phi_{io}$.
This gives that $T_{io}(\phi_{io}) =
T_{o}^{setp} + (\langle T_{i}\rangle - \langle T^{setp}\rangle )$.
Thus, $f$ can be rewritten as
$\sum_{o=1}^{N}[T_{io} (\Delta F_{io}) - T_{io}( \phi_{io})]^{2}$.
Since $T_{io}$ is a linear function of $\Delta F_{io}$, we have that
$T_{io}(\Delta F_{io}) = T_{io}( \phi_{io}) + \frac{\partial
T_{io}}{\partial \Delta F_{io}}\cdot (\Delta F_{io} - \phi_{io})$, and
hence $f$ becomes $\sum_{o=1}^{N}\left(\frac{\partial T_{io}}{\partial
\Delta F_{io}}\right) ^{2}(\Delta F_{io} - \phi_{io} )^{2}$.
As the reallocation of $m$ does not effect the total (summed) utility,  minimizing $f$ is equivalent to minimizing $-\sum_{o=1}^N u_o$, with  $\alpha_o = \frac{\partial T_{io}}{\partial \Delta F_{io}}$.
Furthermore, we have that any Pareto optimal allocation in a market where the utility functions are described by Eq.~(\ref{eq:properUtility}) maximizes $\sum_{o=1}^N u_o$. (Suppose  that there is an allocation $\Delta F_{io}^a$ that does not maximize $\sum_{o=1}^N u_o$, but that $\Delta F_{io}^b$ does. Then reallocating $\Delta F_{io}$ to $\Delta F_{io}^b$ and letting $m_{io}^b = m_{io}^a + u_o(\Delta F_{io}^a,m_{io}^a)- u_o(\Delta F_{io}^b,m_{io}^b)+\frac{\sum_{o=1}^N u_o(\Delta F_{io}^b,m_{io}^b) - \sum_{o=1}^N u_o(\Delta F_{io}^a,m_{io}^a)}{N}$ is always a Pareto improvement. Hence, a non-maximized sum implies a non-Pareto optimal allocation, and a Pareto optimal allocation implies a maximized sum.)  
Then \cite[Theorem~3.1, p.~44]{Ygge:98Thesis} implies that any Pareto-optimal allocation in a market where the utility functions are described by Eq.~(\ref{eq:properUtility}) with $\alpha_o = \frac{\partial T_{io}}{\partial \Delta F_{io}}$, minimizes $f$.
$\Box$ 
}

Thus, we have constructed a fully distributed market design that yields an optimal outcome. Particularly note that Theorem~\ref{theor:optimal} was not based on the assumption that an integral controller was used, rather it said that if $\phi_{io}$ (the desired resource by the controller) is optimal, then the proposed utility function generates a globally optimal outcome. 

\subsection{Discussion}

Previously, we saw that the independent controller \mbox{\textsc{Control-B}}
that incorporates global data, viz.\ the average temperatures,
performs very well. In the present section we positively answered the
question if one can construct a market, {\sc Market-B}, that is based
on local data only and that performs as well.

For this result we have employed a market approach based on general equilibrium theory. This is of course not the only available mechanism for
resource allocation in multi-agent systems. It seems interesting to try out other
mechanisms, like the contract net protocol \cite{Davis:83a}, and see
if they perform better. However, Theorem~\ref{theor:optimal} tells us that, if we
treat the problem of building control as being separable in terms of
agents (as also done by Huberman and Clearwater), there is no better
scheme.\footnote{We note that, as mentioned earlier, the problem is
actually not fully separable in terms of agents and therefore better
solutions may exist if this is taken into account. Another
observation is that in this article we have investigated only the case
of using the currently available resource as the interesting commodity, in accordance with the work of Huberman and Clearwater, and we found an optimal mechanism for
that. We note however that extending the negotiations to future resources
as well could potentially increase performance. But this is a
different problem setting with different demands on available local
and/or global information items, such as predictions. We have given a solution to this problem in recent work, see Ygge et al.~\citeyear{Ygge:99PAAM}.}
For example, if we assigned all the resources to an auctioneer, that on
its turn would iteratively assign the total resource in small portions to bidders
bidding with their true marginal utility, we would end up with
something close to the competitive equilibrium, but we cannot do
better than \mbox{\textsc{Market-B}}. Furthermore, this would be a computationally extremely
inefficient way to arrive at equilibrium compared to other available
methods~\cite[Chapter~4]{Ygge:98Thesis}. That is, we can use different
mechanisms for achieving the competitive equilibrium, but we can never
hope to find a mechanism that would do better than the
\mbox{\textsc{Market-B}} scheme.

\newpage

\section{Conclusions}
\label{sec:conclusions}

We believe that both the approach and the results, as presented in
this article, pose an interesting challenge to the software agent community. Multi-agent
systems offer a new way of looking at information systems development,
with a potentially large future impact. However, new approaches must prove their value in comparison
and competition with existing, more established ones. The agent paradigm
is no exception.

We have therefore deliberately played the role of the devil's advocate
in this article. In our view, a key question not yet satisfactorily answered by the software agent community is: in what
respect and to what extent are multi-agent solutions better than their
more conventional alternatives? This article has shown 
that arguing in favor of the multi-agent systems approach does
require careful analysis beyond the disciplinary boundaries of computer science. Empirical and comparative
studies in the multi-agent literature of the kind carried out in the present
article are all too rare as yet. But as we have shown in technical detail, established paradigms such as
conventional central control cannot be that easily dismissed. 
A similar argument holds, by the way, regarding mathematical optimization techniques in distributed
resource allocation problems, cf. our previous discussions~\cite{Ygge:96a,Ygge:98Thesis}. Many of them are, in a distributed guise, better than many newly proposed market protocols. 

Abstract considerations alone, concerning the
general nature of agenthood, autonomy, rationality, or cooperation, are not
sufficient to prove the value of the agent paradigm. Such theoretical reflections are worthwhile, but 
do not diminish the need for thorough analysis of (agent and market)
failures {\em and} successes in real-life applications.
Therefore, we have taken a different
approach, aimed at obtaining experimental data points on the basis of which
convincing software agent claims can be established. 

The data point considered in
this article is climate control within a large building consisting of
many offices. Given a measure, Eq.~(\ref{eq:stddev}), a local controller approach, Eq.~(\ref{eq:controller}), current temperatures, and the setpoint temperature, we have investigated the problem on how to properly distribute the resource among the offices.  This is a rather prototypical application relating to the
general problem of optimal resource allocation in a highly distributed
environment. This class of problems has already received much
attention in the multi-agent area. Reportedly, this type of application is
very suitable for market-oriented programming \cite{Huberman:95a}. On
the other hand, we have devised some better conventional control
engineering solutions, as well as alternative and better market designs.

The main conclusions of our investigation are:

\begin{itemize}

\item The market approach by Huberman \& Clearwater \citeyear{Clearwater:94a,Huberman:95a} indeed outperforms a
standard control solution based on local, independent controllers. So,
the market-based multi-agent approach indeed yields a working solution to this type of
problem. Our analysis has shown that the success of this market approach depends on the agents communicating their local information to all other agents before the auction starts.

\item However, if conventional central control schemes are allowed to exploit the same 
global information, they perform even better.

\item We have proposed an alternative market design based on general equilibrium theory that uses local
data only. It performs better than the Huberman-Clearwater market and as well as a centralized control scheme
having access to global information.

\item Our general conclusion can be formulated as a quasi-equation: {\em ``local information + market
communication = global control''}. This holds under suitable conditions (existence of market equilibrium, price-taking agents) and its validity has been specifically shown here for the case of building climate control (compare particularly the {\sc Control-B} and the {\sc Market-B} schemes we developed). However, as we intend to show in forthcoming work, this is a much more generally valid result.

\item The important difference is
that in computational markets this global information is an
{\em emergent property} rather than a presupposed concept, as it is in
central control.

\end{itemize}

In our analysis we have focused on the market approach. It is tempting
to ask whether things are different when a non-market multi-agent approach is
followed, say, using the contract net \cite{Davis:83a}. As we argued,
the answer in our opinion is a straightforward {\em no}. The
goal in the considered class of problems is to find the optimal
distributed solution. Alternative agent approaches, market as well as
non-market ones, only change the multi-agent dynamics on the way to
this goal. This might be done in a better or poorer way, but it is not
possible to change this goal itself. The goal state in any multi-agent
approach is, however formulated, equivalent to market equilibrium, the
yardstick for having achieved it is given by some quantitative
performance measure as we discussed, and both are stable across
different agent approaches.

Thus, one of the main conclusions of this article is that one must be very careful when promoting multi-agent approaches to resource allocation problems for which traditional approaches are available. In particular, one should be cautious using arguments related to distribution of information (as was done by Huberman and Clearwater), or other computational aspects. Still, we argue that there \emph{are} conceptual advantages of market-based approaches to this type of problems, as well as other advantages such as evaluation of local performance (cf. Section~\ref{sec:mop}). These advantages do not show off very clearly in the present application setting -- for example, it was assumed that all offices have the same thermal characteristics and office agents on the market are not added and deleted continuously on the fly -- but they are clearly visible in other more general settings. 

A final note is that in this article we have devised an \emph{optimal market design given the problem formulation} rather than devised \emph{an optimal approach to the general problem of building control}. 
This is in line with the objective of this paper to give a comparative study of different possible approaches. That is, we have focused on a published and well-known problem formulation in order to focus on the subject of markets for resource allocation alone. As stated earlier in the article, several aspects can be improved, for example:
\begin{itemize}
\item The local controllers. I-controllers are seldom used, rather PI- or PID-controllers are preferred. Furthermore, for these kind of computerized settings, modern digital controllers, based on e.g. pole-placement methods are preferable~\cite{Astrom:90Computer}.
\item The measure. The average value is at least as important as the standard deviation. (We have as a consequence excluded pathological solutions from our analysis by taking the average temperature as given in Theorem~\ref{theor:optimal}).
\item The incentives for office agents to reveal their true preferences in order to avoid speculation. Reasonably, personnel in the offices should have the opportunity to make trade-offs between comfort and economical value. (It has been shown that generally speaking it is very difficult to benefit from speculation if the number of agents on the market is sufficiently large, and/or if uncertainty about the other agents' behavior exists~\cite{Sandholm:97IJCAI}.)
\item Taking several time periods into account. As each office serves as a storage for heat, agents can for example gain by using relatively much resource during certain hours when the total resource need is small.
\end{itemize}

That is, a more realistic approach to the building control problem is to use minimized cost as the measure, give the users real incentives to reveal their energy preferences (by letting them pay their actual energy costs so that attempted speculation will generally cost money), and take future time periods into account. Elsewhere we have solved the problem of dealing with simultaneous optimization over different time periods, by means of a multi-commodity market~\shortcite{Ygge:99PAAM}.

In such a more realistic and large-scale setting, the market-based approach is attractive compared to its alternatives. The abstractions used (prices and demands) are natural and easily understood by everyone, and they are uniform over all types of agents (even ones that do not use the resource for controlling a temperature). 

A major qualitative conclusion of this article is that ``local data plus market communication yields global control''. This conclusion is based on the discussed application setting of building control, as an instance of a distributed resource allocation problem. It suggests that generally for this type of problem both central control engineering and multi-agent market solutions can be devised that give comparable optimal control quality. A next step is to prove this more generally in a rigorous mathematical fashion, delineating the preconditions in more detail. Such a proof can be based upon the (continuous and matrix-algebraic) dynamic systems theory available from control engineering, and especially upon results concerning what is called optimal control. We believe that this indeed can be done in a formal way, and \emph{as a conjecture we state the following general result}.  Multi-agent equilibrium markets yield optimal decentralized solutions to distributed resource allocation problems that are of the same quality, in terms of a given overall systems performance index, as solutions given by the optimal central (multi-input, multi-output) systems controller that has access to all relevant local data. These local data involve the total system state and control vectors (in building control these are the vectors formed from the difference between the actual and setpoint temperatures for each office, and the cooling power for each office, respectively). Preconditions for this to be true are: (i) agents act competitively; (ii) the equilibrium exists; (iii) the systems performance index can be written as a linear combination of local contributions (implying diagonality of certain matrices; if not, agents are not independent). 
These local contributions are directly related to the agents' utility functions. The agent approach will be more readily generalizable to large-scale systems and non-linear control solutions (linearity is the main case where control engineering can get analytical mathematical expressions). This is indeed a strong and general statement about the relationship (and even outcome equivalence) between decentralized markets and central control. 

\section*{Acknowledgments}
The present work was mainly carried out at the University of Karlskrona/Ronneby.
We thank Rune Gustavsson and
Hans Ottosson for all their support. A special
acknowledgment goes to Olle Lindeberg whose very detailed comments on
the draft papers led to significant improvements in the simulations
and whose ideas also helped us in the design of the market in
Section~\ref{sec:marketB}. We benefit significantly from several discussions with Michael Wellman. We also thank Bengt Johannesson, who, as a
part of his master's thesis, went through all details of this article and
independently recreated and verified all the simulations. We thank Arne Andersson, Eric Astor, and
the SoC team for useful
comments and discussions of draft material. This work was partially sponsored by NUTEK and EnerSearch AB.

An earlier version of this paper was presented at the  MAAMAW'97 workshop~\cite{Ygge:97MAAMAW}.

\newpage

\appendix

\section{Original Formulation of the Huberman-Clearwater Market}
\label{sec:orgform}

All formulae in this section were directly taken from the papers by Huberman \& Clearwater~\citeyear{Clearwater:94a,Huberman:95a}.

\paragraph{Trade volumes}
First, the decision for an agent to buy or sell is based on
\begin{equation}
   t_{io} = \frac{T_{o}^{setp}}{T_{io}}\cdot
            \frac{\langle T_{i}\rangle}{\langle T^{setp}\rangle}
            \,\,\,\left\{ \begin{array}{ll}
   t_{io}>1, & seller \\
   t_{io}<1, & buyer \end{array}\right..
\label{eq:buyorsell}
\end{equation}

Then, the total trade volume, $V$, is calculated from
\begin{equation}
       V_{i} = \sum_{o=1}^{N} \left| 1 - t_{io} \right| ,
\label{eq:tradeVol}
\end{equation}
where N is the number of offices.

Every agent calculates its request volume, $v$, according to
\begin{equation}
       v_{io} = \alpha \frac{\left| 1 - t_{io} \right|}{V_{i}}.
\label{eq:rel_vol}
\end{equation}

When an agent buys or sells its $v$ the actual movement of a valve,
called $VAV$, is computed from
\begin{equation}
       \Delta VAV_{io} = f(flow_{io},v_{io},VAV_{io}),
\label{eq:deltaVAV}
\end{equation}
after which the actual $VAV$ position for each interval is updated
according to
\begin{equation}
       VAV_{i+1,o} = VAV_{io} + \Delta VAV_{io}.
\label{eq:VAV}
\end{equation}

The function $f$ in Eq.~(\ref{eq:deltaVAV}) stems from the physics of the office control, but it is not easy to derive in the general case and it is neither explicitly given in the original papers \cite{Clearwater:94a,Huberman:95a}. A reasonable and simple choice is to assume a linear relationship (the cited papers suggest that they do so in practice as well), replacing Eq.~(\ref{eq:deltaVAV}) and Eq.~(\ref{eq:VAV}) by
\begin{equation}
       F_{i+1,o} = F_{io} \pm v_{io},
\label{eq:Ptrade}
\end{equation}
where plus or minus depend on whether it refers to an accepted buy or sell bid. $P_{cio}$ is obtained from Eq.~(\ref{eq:contrToPower}). We have employed Eq.~(\ref{eq:Ptrade}) in our simulations. The nature of this 
assumption is not crucial to our central line of reasoning.

\paragraph{Bids}
The bids are based on a \emph{marginal utility}\footnote{This is called \emph{utility} in the work of Huberman and Clearwater. We prefer to use the term marginal utility instead, because it is directly related to price. This terminology conforms better to that of microeconomic theory.} of the form described by\footnote{This notion of a utility function used by Clearwater and Huberman is very much based on the work of Steiglitz \& Honig~\citeyear{Steiglitz:92}}
\begin{equation}
       U(t_{io}/T^{setp}_{o},m_{io}) =
         [U(0,m_{io})]^{(1-t_{io}/T^{setp}_{o})} =
         [U(0,m_{io})]^{(1-
         \frac{\langle T_{i}\rangle}{T_{io}\langle T^{setp}\rangle})},
\label{eq:c1Utility}
\end{equation}
with
\begin{equation}
       U(0,m_{io}) = u_{3} - (u_{3} - u_{1})e^{-\gamma m_{io}} ,
\label{eq:U0}
\end{equation}
and
\begin{equation}
       \gamma = ln \left[ \frac{u_{3}-u_{1}}{u_{3}-u_{2}} \right],
\label{eq:gamma}
\end{equation}
where $u_{1} = 20$, $u_{2} = 200$, and $u_{3} = 2000$, and $m$ is the
amount of money that an agent has, given by
\begin{equation}
       m_{io} = 100(2-VAV_{io}).
\label{eq:money}
\end{equation}

With the above relation between $F_{io}$ and $VAV$, we rewrite Eq.~(\ref{eq:money}) as 
\begin{equation}
       m_{io} = 100(2 - \frac{F^{max}_{o} - F_{io}}{F^{max}_{o}}).
\label{eq:mymoney}
\end{equation}

Observing Eqs.~(\ref{eq:U0}) and (\ref{eq:gamma}),
we note that these equations can be simplified to
\begin{equation}
\begin{array}{ll}
 U(0,m_{io}) = & u_{3} - (u_{3} - u_{1})e^{-\gamma m_{io}} =
        u_{3} - (u_{3} - u_{1})(e^{\gamma})^{-m_{io}} = \\
        & u_{3} - (u_{3} - u_{1})
        \left( \frac{u_{3} - u_{1}}{u_{3} - u_{2}}\right) ^{-m_{io}}.
 \end{array}
\label{eq:SimpU0}
\end{equation}

The bids are calculated from multiplying the marginal utility with
the previous price, $price$, according to
\begin{equation}
       B_{i,o} =
       U_{io}(t_{io}/T^{setp}_{o},m_{io})\cdot price_{i}.
\label{eq:bid}
\end{equation}

This is the equation given by Huberman and Clearwater. Straightforward application of Eq.~(\ref{eq:bid}) turns out to produce major problems in simulations, however.
Equation~(\ref{eq:c1Utility}) shows that $U(t_{io}/T^{setp}_{o},m_{io})$
is minimized for minimized $T_{io}$ and maximized
$\frac{\langle T_{i}\rangle}{\langle T^{setp}\rangle}$. As we can
expect $T_{io}$ to be well above $10^\circ C$ and
$\frac{\langle T_{i}\rangle}{\langle T^{setp}\rangle}$ to be well
below 2, and $U(0,m) \approx 2000$, 
we can be sure that $U(t_{io}/T^{setp}_{o},m_{io})$ will be
well above $2000^{1-\frac{2}{10}} \approx 437$. Thus, the bidding
price will never be below 437. Then, Eq.~(\ref{eq:bid}) tells us that
the market price will be at least $price_{0}\cdot 437^{i}$. This
leads to numerical overflow after a few iterations. We note however that, since all agents
multiply their bids with the previous price, this has no effect on the
reallocation itself: it affects only the price level. Therefore, we
omit multiplying by the previous price in our simulations, so that the agents' bid prices in Eq.~(\ref{eq:bid}) equal their marginal utilities of Eq.~(\ref{eq:c1Utility}). Huberman and Clearwater state that they burn all money after each auction round in order to avoid inflation and overflow, indicating that they may adopt a similar procedure. In any case, this procedure leads to exactly the same allocations but avoids numerical overflow.

\newpage

\bibliography{yggenw}
%\bibliographystyle{unsrt}
\bibliographystyle{theapa} 

\end{document}
