% Paper for Journal of Artificial Intelligence Research
% Draft version June 16th, 1997
% Fredrik Ygge and Hans Akkermans
\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:} {\tt #1}}
\newcommand{\hacom}[1]{{\bf Hans comments:} {\tt #1}}
\newcommand{\fyrep}[2]{{\bf Fredrik suggests, replace:} { \tt #1}{\bf with:} {\tt #2}}
\newcommand{\harep}[2]{{\bf Hans suggests, replace:} {\tt #1} {\bf with:} {\tt #2}}
\newtheorem{prop}{Proposition}
\openlinepar
\psdirectories{figs,icmfigs,dadsmfig,c:/text/dadsm-96/figs}
\begin{document}
\title{\bf Duality in Multi-Commodity Market Computations }
\author{%
{\bf Fredrik Ygge} \footnotemark[3]
\and
{\bf Hans Akkermans} \footnotemark[4]
}
\date{%
\footnotemark[3]\
EnerSearch AB and University of Karlskrona/Ronneby \\
Department of Computer Science (IDE) \\
372 25 Ronneby, Sweden \\
Fredrik.Ygge@ide.hk-r.se,
http://www.enersearch.se/$\ \tilde{}\ $ygge \\[12pt]
%
\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 \\[12pt]
%
%{\em To appear in \\
%Proceedings MAAMAW'97, \\
%LNCS Series, Springer-Verlag, Berlin, D, \\
%held in Ronneby, Sweden, 13--16 May 1997}
}
\maketitle
\begin{abstract}
In search for general equilibrium in multi-commodity markets,
price-oriented schemes are normally used. That is, a set of prices
(one price for each commodity) is updated until supply meets demand for each
commodity. It is well known that in a two-commodity market
resource-oriented schemes are conceivable. In this paper we
demonstrate the duality between price- and resource-oriented schemes
in the general multi-commodity case. We also discuss important
properties of the two approaches.
In resource-oriented schemes the resource constraint, which says that
supply must equal demand, is always fulfilled, implying that at any
time the auctioneer can provide a feasible allocation. This is not the
case in price-oriented schemes outside market equilibrium. In this
paper we introduce a novel any-time algorithm, \textsc{Proportion},
for the price-oriented scheme as well, that allows the auctioneer to
deliver a suitable allocation at some deadline (possibly unknown in
advance) also before market equilibrium is reached. We also show how
the findings for the any-time algorithms can enable more efficient
price-oriented markets.
\end{abstract}
\section{Introduction}
In our human society, resource (re)allocations are often performed
through markets. This includes resource allocation on many different
levels and on many different scales, from our daily grocery shopping
to large trades between big companies and/or nations. The market
approach to resource allocation in human society has inspired the
Multi-Agent Systems (MAS) community to construct similar concepts for
MAS, where the trade is performed between computational agents on
\emph{computational markets}. Wellman~\cite{Wellman:93a} refers to the
approach of using prices as interfaces to resources for analysis and
design of resource allocation in distributed systems as a programming
paradigm, and uses the notion of \emph{market-oriented programming}.
A common approach to implement computational markets is to use a
mechanism that obtains \emph{general equilibrium}, like done by Cheng
and Wellman \cite{Cheng:97a}, and this is also the market approach
investigated here. General equilibrium obtains when a set of prices
(one price for each commodity) is found such that supply meets demand
for each commodity and the agents optimize their use of resource at
the current price level. Here we will demonstrate how general
equilibrium can be reached \emph{both} through iterating over prices
and iterating over resources.
To make market-oriented programming successful, it is of vital
importance to incorporate available knowledge from economic theory
\cite{Wellman:96a} and game theory \cite{Sandholm:97a}. At the same
time it is, as argued before \cite{Ygge:96a,Andersson:98a}, also
important to study efficient implementations of computational markets.
As many resource allocation problems face real-time constraints, one
interesting issue is to investigate any-time algorithms for
computational markets. In the present paper we show how any-time
algorithms can be constructed also when the search for general
equilibrium is performed over prices. As a side result of our research
to construct any-time algorithms, we discovered phenomena that
potentially reduce the computational costs for the search over prices
significantly.
Throughout the paper we assume the resource to be infinitely divisible
(i.e., continuous). We also assume that there are upper and lower
bounds on how much resource each agent can take. The main application
that we have in mind for the research described here is power load
management~\cite{Ygge:96a}, but the results presented are fully
application independent. We do not discuss convergence conditions of
different algorithms or existence and uniqueness of the general
equilibrium, but refer to other work on those issues
(e.g. \cite{Cheng:97a,Ygge:96a,Kurose:89a,Press:94a,Fletcher:87a,Mas-Colell:95a,Takayama:85a,Shoven:92a}).
\section{Multi-Commodity Search}
In this section we describe the two main approaches for
multi-commodity search and discuss important properties of these
approaches.
\subsection{Price-Oriented Approaches}
The market equilibrium is given by
\begin{equation}
{\mathbf z}({\mathbf p}) = {\mathbf 0},
\label{eq:priceEq}
\end{equation}
where ${\mathbf z}({\mathbf p}) = [z_1({\mathbf p}), z_2({\mathbf p}),
\ldots , z_k({\mathbf p})]^T$, $z_i({\mathbf p})$ being the aggregate
excess demand for commodity $i$, ${\mathbf p} =
[p_1, p_2, \ldots ,p_k]$ where $p_i$ is the price for commodity $i$,
and $k$ is the number of commodities. In a price-oriented scheme the
price vector is updated until Eq.~(\ref{eq:priceEq}) is fulfilled.
Since prices are only relative, we set $p_k = 1$, and need only to
search over $k-1$ elements in the price vector. Inputs to the scheme
are the respective net demands of each agent,
${\mathbf z}_{\alpha}({\mathbf p})$, where $\alpha$ denotes an agent.
One example of such an algorithm is \textsc{Walras}~\cite{Cheng:97a}.
Another is a multi-variable Newton search as described by
\begin{equation}
{\mathbf p}^{i+1} = {\mathbf p}^{i} - s \cdot \bigtriangledown
{\mathbf z}^{-1}({\mathbf p}^{i}) \cdot {\mathbf z}({\mathbf p}^{i}),
\label{eq:Newton}
\end{equation}
where $i+1$ and $i$ denote iterations, $s$ is a step size, and
$\bigtriangledown {\mathbf z}({\mathbf p})$ is the gradient matrix
defined by $\bigtriangledown z_{ij}({\mathbf p}) =
\frac{\partial z_i({\mathbf p})}{\partial p_j}$.
The proper value of $s$ can be determined at run-time by a suitable
algorithm~\cite{Press:94a}. The allocation of the $k$th commodity is
obtained from the budget constraint, i.e. $z_{\alpha k} =
-\sum_{j = 1}^{k-1}p_j z_{\alpha j}$.
\subsection{Resource-Oriented Approaches}
Under the assumption that there is a one-to-one relationship between
prices and excess demands, an alternative way to express
Eq.~(\ref{eq:priceEq}) is to reallocate resources between the agents
until
\begin{equation}
p_{\alpha i}({\mathbf z}_{\alpha}) = p_{ni}({\mathbf z}_{n}) ,
\begin{array} {l}
1 \leq \alpha \leq n \\
1 \leq i \leq k
\end{array}
\label{eq:resEq}
\end{equation}
holds. Here, $ p_{\alpha i}({\mathbf z}_{\alpha}) $ is agent
$\alpha$'s price for commodity $i$ at a change in allocation
${\mathbf z}_{\alpha}$, $n$ is the number of agents, and $k$ is the
number of commodities. Thus, each agent $\alpha$ is holding a price
vector ${\mathbf p}_\alpha = [p_{\alpha 1}, p_{\alpha 2}, \ldots ,
p_{\alpha k}]^T$.
For the case with only two commodities, it is well known that
resource-oriented schemes are possible \cite{Ygge:96a,Andersson:98a}.
\footnote{In fact, in \cite{Ygge:96a} we only discussed one commodity
and the other was implicit. For a discussion on the relation between a
utility maximization problem with one commodity and a market with two
commodities refer to ~\cite{Ygge:97MAAMAW}.}
As in the price-oriented case we only need to search over $k-1$
commodities, $p_k=1$, and $z_{\alpha k} =
-\sum_{j = 1}^{k-1}p_j z_{\alpha j}$.
The inputs to the resource-oriented scheme are, for each agent, the
utility function, the endowments and the boundaries
($u_{\alpha}({\mathbf z}_{\alpha})$, ${\mathbf e}_{\alpha}$,
${\mathbf z}_{\alpha}^{l}$ and ${\mathbf z}_{\alpha}^{u})$. The
competitive behavior of an agent holding a quasi-concave utility
function, $u_{\alpha}({\mathbf z}_{\alpha})$, and endowment,
${\mathbf e}_\alpha$, is obtained by setting up the Lagrangian:
\begin{equation}
{\cal L}_{\alpha} = u_{\alpha}({\mathbf z}_{\alpha}) +
\lambda {\mathbf p}_\alpha^T \cdot{\mathbf z}_\alpha ,
\label{eq:Lagrangian}
\end{equation}
and solve the equation system
$\frac{\partial {\cal L}_{\alpha}}{\partial z_{i}} = 0$ and
$\frac{\partial {\cal L}_{\alpha}}{\partial \lambda} = 0$.
\footnote{Note that submitting utility functions and endowments, and
computing equilibrium from competitive behaviour, does not prevent
agents from speculating~\cite{Hurwicz:86a}. Agents can still speculate
by giving false utility functions, similar to how agents can speculate
when submitting demand functions in the price-oriented case. In small
markets, agents that have both detailed and accurate knowledge about
other agents can gain by such speculation~\cite{Sandholm:97a}.}
Accordingly, we get
\begin{equation}
\frac{\partial u_{\alpha}}{\partial z_{i}} =
\lambda p_{\alpha i} ,
\label{eq:margUtil}
\end{equation}
for all commodities $i$. It immediately follows that
\begin{equation}
\frac{\frac{\partial u_{\alpha}}{\partial z_{i}}}
{\frac{\partial u_{\alpha}}{\partial z_{k}}} = p_{\alpha i},
\; 1 \leq i \leq k-1,
\label{eq:partialL}
\end{equation}
where we have used the fact that $p_{\alpha k} = 1$.
Now we introduce a vector ${\mathbf f}$, defined by
${\mathbf f} = [{\mathbf p}_{1}({\mathbf z}_{1}) -
{\mathbf p}_{n}({\mathbf z}_{n}),
{\mathbf p}_{2}({\mathbf z}_{2}) -{\mathbf p}_{n}({\mathbf z}_{n}),
\ldots , {\mathbf p}_{n-1}({\mathbf z}_{n-1}) -
{\mathbf p}_{n}({\mathbf z}_{n})]^T$.
Then ${\mathbf f} = {\mathbf 0}$ is equivalent to (\ref{eq:resEq}).
A standard multi-variable Newton method for solving this equation
is then given by
\begin{equation}
{\mathbf z}^{i+1} = {\mathbf z}^{i}-s \cdot \left( \bigtriangledown
{\mathbf f}({\mathbf z}^{i})\right)^{-1}
\cdot {\mathbf f}({\mathbf z}^{i}),
\label{eq:resNewton}
\end{equation}
where $s$ is a step size, and $z_{\alpha j}$ denotes the change in
agent $\alpha$'s allocation of commodity $j$.
From the feasibility constraint we get that
${\mathbf z}_n = -\sum_{\alpha=1}^{n-1}{\mathbf z}_\alpha$ and thus
\begin{equation}
\bigtriangledown f_{ij} =
\left\{ \begin{array}{ll}
\bigtriangledown {\mathbf p}_i({\mathbf z}_i) + \bigtriangledown
{\mathbf p}_n({\mathbf z}_n), & i = j \\
\bigtriangledown {\mathbf p}_n({\mathbf z_n}), & i \neq j
\end{array}.
\right.
\label{eq:gradF}
\end{equation}
Due to the symmetric appearance of $\bigtriangledown {\mathbf f}$, it
can be inverted analytically by hand and Eq.~(\ref{eq:resNewton}) can
be reduced to the following expression for the update of each agent
(see proof in Appendix~\ref{app:NewtProof}):
\begin{equation}
{\mathbf z}_\alpha^{i+1} =
{\mathbf z}_\alpha^{i}-s \cdot \Diamond {\mathbf p}_\alpha^i
\left ({\mathbf p}_\alpha^i-{\mathbf p}_n^i-\bigtriangledown
{\mathbf p}_n^i\left(\sum_{\beta=1}^n
\Diamond {\mathbf p}_\beta^i\right)^{-1}
\Diamond{\mathbf p}_n^i\sum_{\beta=1}^n
\Diamond {\mathbf p}_\beta^i
\left({\mathbf p}_\beta^i-{\mathbf p}_n^i\right)
\right),
\label{eq:closedResNewton}
\end{equation}
where ${\mathbf p}_\alpha^i$, $\bigtriangledown {\mathbf p}_\alpha^i$,
and $\Diamond {\mathbf p}_\alpha^i$ are abbreviations for
${\mathbf p}_\alpha({\mathbf z}_\alpha^i)$,
$\bigtriangledown {\mathbf p}_\alpha({\mathbf z}_\alpha^i)$, and
$\left( \bigtriangledown
{\mathbf p}_\alpha({\mathbf z}_\alpha^i)\right)^{-1}$, respectively.
The term ${\mathbf p}_n^i+\bigtriangledown
{\mathbf p}_n^i\left(\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\right)^{-1}
\Diamond{\mathbf p}_n^i\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\left({\mathbf p}_\beta^i-{\mathbf p}_n^i\right)$
can be interpreted as the expected price which we denote by
$\langle {\mathbf p} \rangle$.
This would have been the equilibrium price if the current value of
$\bigtriangledown {\mathbf p}$ would hold everywhere.
With only two commodities (\ref{eq:closedResNewton}) reduces to
\begin{equation}
z_{\alpha 1}^{i+1} = z_{\alpha 1}^{i} - s
\frac{p(z_{\alpha 1}^i)-
\frac{\sum_{\beta=0}^{n}
\frac{p(z_{\beta 1}^i)}{ p'(z_{\beta 1}^{i})}}
{\sum_{\beta=0}^{n}
\frac{1}{ p'(z_{\beta 1}^{i})}}}{p'(z_{\alpha 1}^i)},
\label{eq:twoNewton}
\end{equation}
which is what was used in~\cite{Kurose:89a} and~\cite{Ygge:96a}
(except for the fact that in those papers only one commodity was explicit
and therefore the marginal utility was used instead of the price, and
the absolute allocation, $x$, was used instead of the change in
allocation, $z$). The allocation of the $k$th commodity is, as in the
price-oriented case, obtained from the budget constraint, i.e.
$z_{\alpha k} = -\sum_{j = 1}^{k-1} \langle p_j \rangle z_{\alpha j}$.
One of the most delicate issues in resource-oriented schemes is the
management of the boundaries. We will look at two different cases --
the cases where
\begin{enumerate}
\item at least one commodity is unbounded, and
\item all commodities are bounded.
\end{enumerate}
We believe the case where at least one commodity is unbounded to be a
very realistic one. For example, it is possible to buy a car for more
money than you possess through taking a loan. So within a reasonably
wide range, we can assume money to be unconstrained. Some people might
be very reluctant to take a loan -- they have a big
decrease in total utility for a negative value of money -- but there is
still no hard constraint. For example, if they had the opportunity,
most people probably would accept taking a loan of \$100,000 if they
had the opportunity to buy a ten million dollar house for that amount
of money now or never. Convinced that it can be sold the day after
with a considerable profit, taking the loan is acceptable.
In the case where at least one commodity is not bounded, the procedure
is to order the commodities such that an unbounded commodity becomes
the $k$th commodity, i.e. the commodity which price can be set equal
to one. For all other commodities, a \textsc{Relax}
scheme~\cite{Ibaraki:88a} is used. That is, first solve as if there
were no boundaries, and then, for all commodities that happened to end
up outside their boundaries, set to the boundary value and distribute
the remaining resource among the other agents. One suggestion for how
to distribute the rest term is to distribute it in proportion to the
current allocation. In the worst case this may require $n$ iterations,
where $n$ is the number of agents. In practice, however, we can expect
a much better figure, especially after a few iterations when the rest
terms are expected to be small.
Before each iteration, except for the first one, the following
algorithm ensures that only the proper allocations are updated. Some
comments are given after the pseudo-code.
\begin{verbatim}
boolean at_least_one_off_bound[nr_commodities] =
{false, false,..., false};
for each agent alpha
for each commodity i
if ((alpha.allocation(i) == alpha.lower_bound(i)) and
(alpha.price(i) <= expected_price_from_prev_iter(i)))
or
((alpha.allocation(i) == alpha.upper_bound(i)) and
(alpha.price(i) >= expected_price_from_prev_iter(i))))
then
alpha.price_gradient(i,i) = infinity;
alpha.price_gradient(i,j) = 0 for i != j;
else
at_least_one_off_bound[i] = true;
endif
endfor
endfor
for each commodity i
if not at_lest_one_off_bound[i] then
exclude the commodity completely for this iteration
compute the expected price as the average
of the price of the agent at its lower boundary
holding the highest price
and the price of the agent at its upper boundary
holding the lowest price
endif
endfor
run the resource update algorithm
\end{verbatim}
Hence, for each commodity $i$ of an agent $\alpha$ that
should not be affected in the next iteration, the rule is to set
$\left(\bigtriangledown {\mathbf p}_\alpha({\mathbf z}_\alpha)
\right)_{ii} = \infty$.
(In practice, just use a value that is considerably higher than any
gradient element that should be affected. For instance, we have
employed a factor $10^{30}$ in our simulations.)
This ensures that the allocation of that specific commodity will not
be updated during the next iteration. If all agents avoid being
affected with respect to one specific commodity, this commodity should
simply be removed during the next iteration. Then, the expected price
is estimated such that agents being at their lower boundary and giving
a higher price than some agent being at its upper bound will reenter
into the scheme (and correspondingly for reentering agents at the
upper bound).
The general case, when there are boundaries on every resource, is considerably harder, and we do not have an efficient solution for it. A pragmatic approach to the problem might be to let $\partial u_{\alpha}/\partial z_n$ increase very dramatically when being close to, and below, the lower boundary and decrease correspondingly for the upper limit. In this way the allocation for the $k$:th good will be forced not to pass the boundaries.
\subsection{Discussion}
Above we demonstrated how price-oriented as well as resource-oriented
schemes can be used for the search for equilibrium in a
multi-commodity market. The price-oriented scheme takes its
inspiration from price-t\^{a}tonnement, and the resource-oriented
scheme is somewhat related to
quantity-t\^{a}tonnement~\cite{Mas-Colell:95a}.
We saw that the resource-oriented
scheme is somewhat more complicated, but at the same time the inputs
to the two approaches are different. In the first case the demand is
the input and in the latter case the inputs are the utility function,
the endowments and the boundaries. In standard micro-economic theory
the utility function is the primary concept and the demand is derived
from the utility function and the endowments. In the special cases
where this can be done analytically, price-oriented approaches are
normally to prefer. However, in the general case the demand function
can not be analytically derived from the utility function and the
endowments, and then numerical methods must be used for obtaining the
demand. In those cases resource-oriented approaches can be highly
competitive.
\section{Any-Time Algorithms}
For many application areas, like the area of power load management we
are working in \cite{Ygge:96a}, we believe it to be useful to search
for the equilibrium until a certain deadline (that is possibly unknown
in advance), and then give a result, i.e. have an any-time
market algorithm. As resource-oriented approaches always produce
feasible allocations, the allocation computed at each iteration can be
used as a market outcome. (As all allocations of commodity $1$ through
$k-1$ are feasible, it follows that also the allocation of commodity
$k$ is feasible, since $z_k = -\sum_{j = 1}^{k-1}
\langle p_j \rangle \cdot z_j$.)
Consequently, resource-oriented schemes are inherently well suited for
any-time market algorithms. It has been argued in \cite{Kurose:89a}
that resource-oriented schemes are superior to price-oriented schemes
because of this feature. In this section we will introduce a novel
price-oriented any-time algorithm, and thus show that also
price-oriented schemes can be used for constructing any-time
algorithms, in the sense that they also can provide suitable
allocations at each iteration. In our view, this further strengthens
our argument concerning the duality between resource-oriented and
price-oriented market schemes.
The main difference between the intermediate results of price- and
resource-oriented schemes during the search for equilibrium is that in
resource-oriented schemes, intermediate results are always
\emph{feasible} (in the sense that the sum of all demands for each
commodity is always equal to zero), but \emph{not fair} (in that some
agents would have higher utility with some of the intermediate
outcomes than with true equilibrium while others would have lower
utility), whereas price-oriented schemes are neither feasible nor fair
(if we can talk about fairness at all with unfeasible allocations).
Both fairness and feasibility are only obtained at equilibrium and
hence for constructing an any-time price-oriented scheme, we have to
come up with a way to obtain feasible allocations. For this we propose
the \textsc{Proportion} algorithm as described below.
Our algorithm, while performing the summations to test whether
Eq.~(\ref{eq:priceEq}) is fulfilled\footnote{That is, \textsc{Proportion} does not affect the asymptotic complexity of the utilized price-oriented algorithm.}, for each commodity $i$, forms the
two sets $s_{fi}$ and $s_{gi}$ according to:
\begin{equation}
\begin{array}{l}
s_{fi} = \{ \alpha | z_{\alpha i}({\mathbf p}) > 0\} ,\\
s_{gi} = \{ \alpha | z_{\alpha i}({\mathbf p}) < 0\} ,
\end{array}
\label{eq:sets}
\end{equation}
and computes the sums $f_i$ and $g_i$ with
\begin{equation}
\begin{array}{l}
f_i({\mathbf p}) =
\sum_{\alpha \in s_{fi}} z_{\alpha i}({\mathbf p}) , \\
g_i({\mathbf p}) =
-\sum_{\alpha \in s_{gi}} z_{\alpha i}({\mathbf p}) .
\end{array}
\label{eq:sums}
\end{equation}
If $z_{i}({\mathbf p})=0$, the market is in equilibrium for this
commodity and the any-time allocation,
$\tilde{z}_{\alpha i}({\mathbf p})$, for the current iteration is
obtained from
\begin{equation}
\tilde{z}_{\alpha i}({\mathbf p}) = z_{\alpha i}({\mathbf p}).
\label{eq:zeroZ}
\end{equation}
If $z_{i}({\mathbf p})>0$, the any-time allocation for the current
iteration is obtained from
\begin{equation}
\tilde{z}_{\alpha i}({\mathbf p}) = \left\{
\begin{array}{l}
z_{\alpha i}({\mathbf p})- \frac{z_{\alpha i}({\mathbf p})}
{f_{i}({\mathbf p})} \cdot z_i({\mathbf p}), \, \alpha \in s_{fi}\\
z_{\alpha i}({\mathbf p}), \, \alpha \not\in s_{fi}
\end{array}
\right.
.
\label{eq:posZ}
\end{equation}
Finally, if $z_{i}({\mathbf p})<0$, the any-time allocation for the
current iteration is obtained from
\begin{equation}
\tilde{z}_{\alpha i}({\mathbf p}) = \left\{
\begin{array}{l}
z_{\alpha i}({\mathbf p})+ \frac{z_{\alpha i}({\mathbf p})}
{g_{i}({\mathbf p})}
\cdot z_i({\mathbf p}), \, \alpha \in s_{gi} \\
z_{\alpha i}({\mathbf p}), \, \alpha \not\in s_{gi}
\end{array}
\right.
.
\label{eq:negZ}
\end{equation}
In the computations of Eqs.~(\ref{eq:sets}) through (\ref{eq:negZ}),
the $k$th commodity must also be included.
In short, the principle of \textsc{Proportion} is that if there is a
positive aggregate demand for a commodity, each agent having a
positive demand will receive less than it demanded in proportion to
the size of its demand, whereas all agents demanding a zero or
negative amount will receive what they demanded. The corresponding
holds if the aggregate demand is negative. As a simple example, if
every agent has a positive net demand for a certain commodity each
agent will receive zero of that commodity.
Observe that \textsc{Proportion} has the important property of never
violating lower or upper boundaries. An agent is always guaranteed to
receive an amount between zero (i.e. its current allocation) and the
amount it demanded.
\section{Simulations}
In the above we described how to implement any-time algorithms for
multi-commodity markets. The interesting question is how useful the
solutions are before an equilibrium has been reached. In this section
we investigate this issue for one set of examples, but we do think
that the results hold for a wide range of problems.
We use a $10$-commodity market with $25$ agents holding constant
elasticity utility functions, i.e. have utility functions as described
by
\begin{equation}
u({\mathbf x}) =
\left( \sum_{j=1}^{k}\alpha_j^{1-\rho}x_j^\rho\right)^{1/\rho}.
\label{eq:CES}
\end{equation}
The agents are assigned random parameters, $\alpha_j$ and $\rho$, and
random initial allocations. The simulation was performed on $50$
different markets, i.e. sets of parameters and allocations. Both a
Newton method with variable step-size and a
\textsc{Walras}~\cite{Cheng:97a} scheme were used. Figure~\ref{fig:z}
shows the average sum of the absolute value of the excess demand for
the simulation.
\postscript{12cm}{z}{\it The average sum of the absolute value of the
excess demand for a simulation on 50 different 10-commodity markets
with 25 constant elasticity agents.}
The scale on the horizontal axis in Figure~\ref{fig:z} is the number
of iterations for the Newton scheme and for the \textsc{Walras}
scheme it is the number of full cycles over all commodities.
The computation required for each iteration of the Newton
scheme is the computation of the new price as described by
Eq.~(\ref{eq:Newton}) plus the computation required for
\textsc{Proportion}. The computation of one cycle of \textsc{Walras}
includes $10$ binary searches, each requiring approximately $45$--$50$
steps, plus the computation of \textsc{Proportion}. The communication
requirements for the two algorithms are dependent on the
configuration. If the agents are physically distributed and only
capable of sending floating point numbers, then for each iteration of
the Newton scheme, one message containing $110$ floating points is
required (${\mathbf p}_\alpha$ and $\bigtriangledown {\mathbf
p}_\alpha$), while one cycle of the \textsc{Walras} scheme requires
$10$ messages, each containing $m$ floating points where $m$ is the
number of samples of the demand function, typically in the order of
$25$.
We note, therefore, that one should be careful when comparing the
results of the two methods. The main reason for using entire cycles
when presenting the \textsc{Walras} scheme is that the result then is
in the same range as with the Newton scheme, but, of course, an
analysis after the update of each market is also conceivable. We see
that both schemes converge rapidly to equilibrium. With the
\textsc{Walras} scheme the value decreases with approximately one
order of magnitude in five iterations and with the Newton scheme the
decrease is typically more than one order of magnitude for each
iteration.
There is no unique, generally agreed upon, measure for the quality of
non-equilibrium solutions. Here we use two measures that we believe to
be adequate --- the improvement of the utility of the agent that is
worst off after the allocation, and the average utility improvement.
In the presentation these values are normalized against the initial
allocation. The improvement of utility of an allocation is the utility
of that allocation divided by the utility of the initial allocation
minus one. Thus, if, e.g., the utility of a new allocation is $4$ and
the utility with the initial allocation was $2$, the improvement is
$\frac{4}{2}-1=1$. Hence, a negative number means a \emph{decrease} in
utility. Figure~\ref{fig:worst} shows the worst improvement found for
each iteration/cycle in any of the $50$ markets, i.e. the values of
each iteration/cycle are not necessarily from the same market.
\postscript{12cm}{worst}{\it The worst improvement found for each
iteration/cycle in any of the 50 markets.}
Even though this is a very pessimistic view we see that after one
cycle with the \textsc{Walras} scheme there is always a Pareto
improvement and that the same holds after four iterations of the
Newton scheme. (Again the difference between cycles of the
\textsc{Walras} scheme and iterations of the Newton scheme should be
kept in mind.) Hence, very quickly the schemes result in Pareto
improvements. In passing we mention that the improvement of the agent
being worst off in a typical market is \emph{considerably higher} than
the worst case for all $50$ markets.
\postscript{12cm}{avgImp}{\it Average utility improvement.}
The other interesting measure, the average utility improvement, is
shown in Figure~\ref{fig:avgImp}.
From Figure~\ref{fig:avgImp} we see that the increase in average
utility is largest during the first few iterations/cycles. This is a
very interesting result, not only from the point of view of any-time
algorithms. It does mean, and this seems particularly true for
\textsc{Walras}, that the increase in quality is totally negligable
for a majority of the iterations/cycles. Thus, \textsc{Proportion} can
potentially reduce the computation costs significantly with negligable
loss of quality.
As a numerical example from the simulations, for \textsc{Walras} to
converge to a total aggregate excess demand of $10^{-10}$, $85$ cycles
are typically required. Now of the average utility improvement gained
during the $85$ cycles, $99.47$\% was gained during the first $5$
cycles and $99.96$\% was gained during the first $10$ cycles. We also
note that when \textsc{Proportion} has been applied after $5$ cycles,
the total aggregate demand is in the order of $10^{-17}$, which is a
\emph{much better} figure than $10^{-10}$ which was obtained after
$85$ iterations without applying \textsc{Proportion}.
We conjecture that for a very wide class of problems it is possible to
terminate the algorithm quite early (e.g. through accepting a quite
high total aggregate demand) and utilize \textsc{Proportion} for
obtaining feasibility without any significant loss in quality.
\section{Conclusions}
In this paper we have shown the duality between price- and
resource-oriented schemes for general equilibrium search. We also described how the two schemes can be
used for constructing any-time algorithms. The most important
conclusions of the work are:
\begin{itemize}
\item There is a duality between resource- and price-oriented schemes
for multi-commodity search.
\item The proper choice of algorithm is highly dependent on the
givens, such as whether demand or utility functions are available, and
on convergence properties of different algorithms.
\item As resource-oriented schemes provide feasible allocations for
each iteration, they are inherently well suited as any-time
algorithms.
\item We introduced \textsc{Proportion}, a price-oriented any-time
algorithm, and showed that there is a straightforward way to produce
suitable results at each iteration. Hence, one can implement any-time
algorithms also with price-oriented approaches.
\item The computation costs of a price-oriented scheme can be reduced
significantly with negligable loss of quality by using
\textsc{Proprortion} for obtaining feasibility, instead of iterating
for a close approximation of the true general equilibrium.
\end{itemize}
\section{Source Code}
All source code used for the simulations is accessible through the
world-wide-web from:
\noindent
http://www.enersearch.se/\~{}ygge/
\section*{Acknowledgements}
We thank Hans Ottosson at EnerSearch and Rune Gustavsson at the University of Karlskrona/Ronneby for all their support.
\appendix
\section{Proof for Resource-Oriented Newton Scheme}
\label{app:NewtProof}
In this appendix we prove that
$$
{\mathbf z}^{i+1} = {\mathbf z}^{i}-s \cdot
\left( \bigtriangledown
{\mathbf f}({\mathbf z}^{i})\right)^{-1} \cdot
{\mathbf f}({\mathbf z}^{i}),
$$
with
$$
\begin{array}{ll}
{\mathbf f} = &
[{\mathbf p}_{1}({\mathbf z}_{1}) -
{\mathbf p}_{n}({\mathbf z}_{n}),
{\mathbf p}_{2}({\mathbf z}_{2}) -
{\mathbf p}_{n}({\mathbf z}_{n}), \ldots , \\
&
{\mathbf p}_{n-1}({\mathbf z}_{n-1}) -
{\mathbf p}_{n}({\mathbf z}_{n})]^T,
\end{array}
$$
can be reduced to
$$
{\mathbf z}_\alpha^{i+1} =
{\mathbf z}_\alpha^{i}-s \cdot \Diamond {\mathbf p}_\alpha^i
\left({\mathbf p}_\alpha^i-{\mathbf p}_n^i-\bigtriangledown
{\mathbf p}_n^i\left(\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\right)^{-1}\Diamond
{\mathbf p}_n^i\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\left({\mathbf p}_\beta^i-
{\mathbf p}_n^i\right)\right),
$$
where ${\mathbf p}_\alpha^i$,
$\bigtriangledown {\mathbf p}_\alpha^i$, and
$\Diamond {\mathbf p}_\alpha^i$ are abbreviations for
${\mathbf p}_\alpha({\mathbf z}_\alpha^i)$,
$\bigtriangledown {\mathbf p}_\alpha({\mathbf z}_\alpha^i)$, and
$\left( \bigtriangledown {\mathbf p}_\alpha({\mathbf z}_\alpha^i)
\right)^{-1}$ respectively.
First introduce the matrices ${\mathbf A}$, ${\mathbf S}$,
${\mathbf T}$, and ${\mathbf R}$ of dimension $(n-1\times n-1)$,
defined by
$$
A_{rc} = \left\{
\begin{array}{ll}
\bigtriangledown {\mathbf p}_r^i, & r = c \\
{\mathbf 0}, & r \neq c
\end{array},
\right.
$$
$$
S_{rc} = \left\{
\begin{array}{ll}
{\mathbf E}, & r = c \\
{\mathbf 0}, & r \neq c
\end{array},
\right.
$$
$$
T_{rc} = \left\{
\begin{array}{ll}
{\mathbf E}, & c = 1 \\
{\mathbf 0}, & c \neq 1
\end{array},
\right.
$$
and
$$
R_{rc} = \left\{
\begin{array}{ll}
\bigtriangledown {\mathbf p}_n^i, & c = 1 \\
{\mathbf 0}, & c \neq 1
\end{array},
\right.
$$
where ${\mathbf E}$ is the unit matrix defined by
$$
E_{rc} = \left\{
\begin{array}{ll}
1, & r = c \\
0, & r \neq c
\end{array},
\right.
$$
Then $\bigtriangledown {\mathbf f} = {\mathbf A} + {\mathbf R}
{\mathbf S}{\mathbf T}^T$, and from the Sherman-Morrison
formula~\cite{Golub:91a} we have that $\left(\bigtriangledown
{\mathbf f} \right)^{-1} =
{\mathbf A}^{-1}-{\mathbf A}^{-1}
{\mathbf R}{\mathbf U}^{-1}{\mathbf T}^T{\mathbf A}^{-1}$ where
${\mathbf U} =
{\mathbf S}^{-1}+{\mathbf T}^T{\mathbf A}^{-1}{\mathbf R}$.
Since the inversion of $\bigtriangledown {\mathbf f}$ now only
contains inversion of diagonal matrices, it can be done analytically.
The result is
$$
\left( \bigtriangledown
{\mathbf f}({\mathbf z}^i \right)^{-1}_{rc} =
\left\{
\begin{array}{ll}
\Diamond{\mathbf p}_r^i \left({\mathbf E} - \bigtriangledown
{\mathbf p}_n^i \left(\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\right)^{-1}\Diamond {\mathbf p}_n^i\Diamond
{\mathbf p}_c^i\right), & r = c \\
-\Diamond{\mathbf p}_r^i \bigtriangledown {\mathbf p}_n^i
\left(\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\right)^{-1}\Diamond
{\mathbf p}_n^i\Diamond {\mathbf p}_c^i, & r \neq c
\end{array}
\right.
$$
Then, the change in the net demand for agent $\alpha$ is
\begin{eqnarray}
&& \Delta z_\alpha = \nonumber\\
&& - s \cdot \Diamond {\mathbf p}_\alpha^i \cdot
\left({\mathbf E} - \bigtriangledown
{\mathbf p}_n^i\left(\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\right)^{-1}\Diamond{\mathbf p}_n^i
\Diamond {\mathbf p}_j^i\right)({\mathbf p}_\alpha^i -
{\mathbf p}_n^i) \nonumber\\
&& + s \cdot \Diamond {\mathbf p}_\alpha^i \cdot
\left( \sum_{1 \leq \gamma \leq n-1\wedge \gamma \neq \alpha}
\bigtriangledown {\mathbf p}_n^i\left(\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\right)^{-1}\Diamond{\mathbf p}_n^i \Diamond
{\mathbf p}_\gamma^i\right) \left({\mathbf p}_\gamma^i-
{\mathbf p}_n^i\right) \nonumber\\
&& = \nonumber\\
&& - s \cdot \Diamond {\mathbf p}_\alpha^i \left
({\mathbf p}_\alpha^i-{\mathbf p}_n^i-\bigtriangledown
{\mathbf p}_n^i\left(\sum_{\beta=1}^n\Diamond
{\mathbf p}_\beta^i\right)^{-1}
\Diamond{\mathbf p}_n^i\sum_{\gamma=1}^n\Diamond
{\mathbf p}_\gamma^i
\left({\mathbf p}_\gamma^i-{\mathbf p}_n^i\right)\right)
. \nonumber\\
\Box && \nonumber
\end{eqnarray}
\bibliography{ygge}
%\bibliographystyle{unsrt}
\bibliographystyle{named}
%\bibliographystyle{plain}
\end{document}