% Paper for IJCAI'97
% Draft version
% Fredrik Ygge and Tuomas Sandholm
%For compilation at Fredrik's site:
\documentstyle[epsf,ijcai97]{article}
%For compilation at Tuomas' site:
%\documentstyle[epsf,$HOME/sty/ijcai95]{article}
%\setlength\titlebox{1.9in}
%%\setlength\textheight{9.8in}%9.375
% Note: these are commands specifically defined in local.sty
%\openlinepar
%\twocolumn
%\psdirectories{figs,icmfigs,dadsmfig,c:/text/dadsm-96/figs}
%\title{\bf \vspace{-0.4in} On the Gains and Losses of Speculation in Equilibrium Markets}
\title{\bf On the Gains and Losses of Speculation in Equilibrium Markets}
\author{ \textbf{Tuomas Sandholm} \\
Department of Computer Science \\
Washington University \\
% Campus Box 1045\\
One Brookings Drive\\
St. Louis, MO 63130-4899\\
sandholm@cs.wustl.edu
\And
\textbf{Fredrik Ygge} \\
EnerSearch and \\
Department of Computer Science (IDE) \\
University of Karlskrona/Ronneby \\
372 25 Ronneby \\
Fredrik.Ygge@enersearch.se
}
\date{}
\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}{\scriptsize {\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| }
% -------------------
%Add ``excess'' to ``supply'' and ``demand'' decisions and functions???
\begin{abstract}
%\vspace{-0.15in}
In computational markets utilizing algorithms that establish a market
equilibrium (general equilibrium), {\em competitive behavior} is
usually assumed: each agent makes its demand (supply) decisions so as
to maximize its utility (profit) assuming that it has no impact on
market prices.
%
%In markets with an infinite number of agents, each agent is best off
%by acting competitively.
%
However, there is a potential gain from {\em strategic behavior} (via
speculating about others) because an agent does affect the market
prices, which affect the supply/demand decisions of others, which
again affect the market prices that the agent faces.
This paper presents a method for computing the maximal advantage of
speculative behavior in equilibrium markets.
%when the other agents' supply/demand functions are taken as fixed
%(classic competitive behavior by the other agents is a special case of
%this).
Our analysis is valid for a wide variety of known market protocols.
We also construct demand revelation strategies that guarantee that an
agent can drive the market to an equilibrium where the agent's maximal
advantage from speculation materializes.
Our study of a particular market shows that as the number of agents
increases, gains from speculation decrease---often turning negligible
already at moderate numbers of agents. The study also shows that
under uncertainty regarding others, competitive acting is often close
to optimal, while speculation can make the agent significantly worse
off---even if the agent's beliefs are just slightly biased. Finally,
protocol dependent game theoretic issues related to multiple agents
counterspeculating are discussed.
%OLD ABSTRACT THAT WAS MORE ON OUR BELIEFS
%(AND AN ATTEMPT TO BE MORE COMPUTATIONAL):
%We believe that computational agents representing self-interested real
%world parties will deviate from competitive behavior in practice only
%if the potential gain from speculation is sufficiently large compared
%to the cost of the computation or information gathering actions
%required for speculation. We also believe that an agent will not
%speculate when that incurs potentially large losses when estimation
%errors are present, e.g. due to biased beliefs or uncertainty about
%others. This paper describes a method---which applies to many known
%algorithms for reaching the market equilibrium---for determining those
%gains and losses. This enables one to analyze how much agents could
%gain or lose by speculating in a particular system, and it is also
%useful when evaluating different strategies since it allows one to
%determine how close to the optimal strategy they are.
%The analysis of one speculating agent is protocol independent. The
%paper concludes by discussing the issues that arise from multiple
%agents speculating simultaneously. Such results depend on which
%market protocol is used.
%\vspace{-0.15in}
\end{abstract}
\section{Introduction}
%=====================
{\em General equilibrium theory}, a microeconomic market framework,
has recently been successfully adapted for and used in computational
multiagent systems in many application domains, see
e.g.~\cite{Kurose89:Microeconomic,Wellman93:Market,Wellman94,Mullen95:Simple,Ygge96:Power,Cheng97:Walras}.
It provides a distributed method for efficiently allocating goods and
resources among agents. Such a market can have two types of agents,
{\em producers} and {\em consumers}. It has a finite number of {\em
commodities}. The amount of each commodity is unrestricted, and each
commodity is usually assumed arbitrarily divisible. Different
elements within a commodity are not distinguishable, while elements
from different commodities are. Each consumer has a {\em utility
function} which encodes its preferences over different {\em
consumption bundles}, i.e. over vectors. Each element of the vector
describes how much of a given commodity the agent consumes. Each
consumer also has an initial {\em endowment} of the different
commodities. The producers can use some commodities to produce
others. The {\em production vector} of a producer describes how much
of each commodity the agent produces. Net usage of a commodity is
denoted by a negative number. A producer's capability of turning
inputs into outputs is characterized by its {\em production
possibilities set}, which is the set of feasible production vectors.
The producer's profits are divided among the consumers according to
predetermined proportions which need not be equal (one can think of
the consumers owning stocks of the producers).
The market is said to be in {\em general equilibrium} in terms of the
prices on commodities, consumers' consumption decisions, and
producers' production decisions if
\begin{description}
\item{I} markets clear: for each commodity, production plus endowments
equals consumption, and
\item{II} each consumer consumes a bundle of commodities such that the
agent could not afford another bundle of higher utility given its
initial endowments, the current prices, and the profits it receives
from producers, and
\item{III} each producer uses the feasible production vector that maximizes
its profits given the prices.
\end{description}
%Require also convex preferences???
If the production possibilities sets are convex, and the consumers'
preferences are continuous, non-decreasing and locally insatiable,
then at least one such equilibrium {\em
exists}~\cite{Mas-Colell95,Kreps90:Course,Varian92}.~\footnote{If
agents act competitively (as opposed to strategically via
speculation), each general equilibrium is Pareto efficient: no agent
can be made better off---with any methodology for making
decisions---without making some other agent worse off. Such
competitive general equilibria are also stable in the sense of the
{\em core} solution concept of coalition formation games: no subgroup
of agents is motivated to pull out of the general equilibrium and form
their own market.} A sufficient condition for {\em uniqueness} of
such an equilibrium is that the demand for each good is nondecreasing
in the prices of the other goods.
% Explain the Nachbar discussion on the core in the journal version???
%%Tuomas: Previously there was some text here regarding that the
%%general equilibrium is Pareto efficient. This is actually wrong.
%%In a market with an infinite number of agents, the general
%%equilibrium is also a competitive equilibrium, and then
%%it is Pareto efficient and all this you said about core is
%%correct. However, for the situation of finite market size
%%it is not true. See e.g. Varian 1996 for the theory of monopoly
%%which is known to be non-Pareto efficient.
%
%Fredrik: I don't think it is a question of finite vs. infinite. If
%the agents act competitively, the GE is PE even with a finite number
%of agents. But I think we agreed on this on the phone already. I reworded
%the footnote so as to make it right.
The analysis in this paper is based on the assumption that a protocol
is used that establishes a market price for each good such that supply
meets demand, and that reallocation is performed {\em after} these
prices have been established. There are many alternative algorithms
that can be used to find such a general equilibrium. Clearly, if no
such equilibrium exists, no algorithm can find it. In this paper we
analyze the gains and losses of strategic behavior via speculation.
We do this by analyzing the equilibrium. If an equilibrium does not
exist, the agents will not achieve a resource reallocation,
%resources will not be reallocated,
and in that case, the gains and losses of speculation are not well
defined. The equilibrium-based analysis makes our results protocol
independent---as long as the agents exchange goods only after an
equilibrium has been reached. This allows our results to hold for
most market algorithms that have been used to find an equilibrium.
Some of these algorithms are now discussed.
To reach a general equilibrium, the {\em price t\^atonnement process}
is usually used. This is an iterative mechanism, and the trades,
production, and consumption are assumed to occur only after the
process has terminated. At each iteration, the {\em auctioneer} sets a
vector of prices. Then all agents have to declare a vector of how much
they are willing to buy and sell of each commodity at the current
prices. Based on this information, the auctioneer updates the price
vector for the next iteration. Under certain technical conditions,
this process is guaranteed to converge to a general
equilibrium~\cite{Mas-Colell95}. Within computational multiagent
systems, Wellman has developed a general equilibrium based software
system called \textsc{Walras}. As example domains, he has used
\textsc{Walras} in flow routing in a network~\cite{Wellman93:Market},
and in configuration design~\cite{Wellman94}. Wellman discusses how
the latter application fails to meet the assumptions for existence of
a general equilibrium. For example, because some design parameters
are discrete, production possibilities sets cannot be convex. Mullen
and Wellman have applied \textsc{Walras} to a distributed information
network example~\cite{Mullen95:Simple}. The iterative market process
of \textsc{Walras} differs from t\^atonnement. Specifically,
\textsc{Walras} uses asynchronous declarations by the agents, and the
agents bid demand functions (of price) as opposed to just quantities.
This process converges to a general equilibrium~\cite{Cheng97:Walras}.
As in t\^atonnement, trades in \textsc{Walras} only occur after the
market process has terminated.
% IS QUANTITY TATON RESOURCE-BASED/CORRECTLY EXPLAINED???
In addition to the price-based market mechanisms, resource-based
mechanisms exist for reaching the general equilibrium. In such a
resource-based protocol ({\em cf}. {\em quantity
t\^atonnement}~\cite{Mas-Colell95}), the auctioneer sets the
allocation of commodities to agents at each iteration, and agents
report how much more or less they are willing to pay for each
commodity. The auctioneer then takes these declarations into account
in changing the allocation in the next iteration: agents that increase
their willingness to pay get more, and others get less than on the
previous iteration. The algorithm terminates when an equilibrium is
reached. Kurose and Simha have developed a market mechanism---applied
to file allocation---where at each iteration, the agents compute their
marginal worths for resources~\cite{Kurose89:Microeconomic}. Based on
these worths, resources are reallocated at every iteration. This
differs from most other equilibrium approaches where trades only occur
after all iterations have been completed. In Kurose and Simha's
approach, the solution gets better at every iteration, and is
guaranteed to finally converge to the optimum. Recently,
resource-based market mechanisms have been used and thoroughly studied
in electricity distribution~\cite{Ygge96:Power}. A sufficient
condition for the applicability of our analysis to resource-based
approaches is that reallocation is not performed until an equilibrium
has been reached.
Classically in equilibrium markets, the agents are assumed to act {\em
competitively}: they treat prices as exogenous. This means that each
agent makes and reveals its demand (supply) decisions truthfully so as
to maximize its utility (profit) given the market prices---assuming
that it has no impact on those prices. The idea behind this {\em
price-taking assumption} is that the market is so large that no single
agent's actions affect the prices. However, this is paradoxical since
the agents' declarations completely determine the prices. The
price-taking assumption becomes valid as the number of agents
approaches infinity: with infinitely many agents (of comparable size),
each agent is best off acting competitively since it will not affect
the prices.
However, in markets with a finite number of agents, an agent can act
strategically, and potentially achieve higher utility by over/under
representing \cite[pp. 220-223]{Malinvaud85:Lectures},
\cite{Hurwicz86:Informationally}. In doing so, the agent has to
speculate how its misrepresentation affects the market prices, which
are simultaneously affected by how other agents respond to the prices
which changed due to the first agent's strategic actions. This paper
addresses the question of how much an agent can gain or lose by such
strategic behavior in such a complex setting of interrelationships.
The theory in this paper stems from well established principles in
microeconomics---such as general equilibrium theory and the theory of
optimal price setting in oligopoly and monopoly markets---and is
extended for situations where agents have estimation errors in their
beliefs regarding the behavior of other agents. First, a general,
protocol independent study of the potential gains and losses from
speculation is presented in Section~\ref{sec:generalMethod}. This is
concretized for the case where only one agent is speculating under
perfect information in Section~\ref{sec:perfectInfo}, and under biased
beliefs about others in Section~\ref{sec:uncertainty}. Simultaneous
speculation by multiple agents is game theoretically discussed in
Section~\ref{sec:protocols}. Finally, Section~\ref{sec:conclusions}
concludes. Note that all numerical utility values in this paper have
been multiplied by 100 for readability. In all, we believe that the
methodology presented in this paper is important for builders of
computational markets where the agents represent self-interested real
world parties that can tailor their agents so as to take advantage of
the other agents in the system.
\section{A Method for Analyzing the Potential Gains from Speculation}
%====================================================================
\label{sec:generalMethod}
The goal of a self-interested consumer is to find the consumption
bundle that maximizes its utility. To find the optimal bundle when
acting in an equilibrium market, the consumer must speculate how other
agents respond to prices. This is because its demand decisions affect
the prices, which affect the demand and supply decisions of others,
which again affect the prices that the consumer faces. Using the
model of other agents, the consumer computes its optimal demand
decisions. Note that other agents might also be speculating (in the
same way or some other, suboptimal way). That is included in the
agent's model of the other agents.
The goal of a self-interested producer is to find the production
vector that maximizes its profits.~\footnote{This makes the standard
assumption that the producer is able to alter its production plan
costlessly during the search for equilibrium.} Again, this requires a
model of how others react to prices because the producer's production
decisions affect the prices, which affect the demand and supply
decisions of others, which again affect the prices that the producer
faces.
% Fredrik: I took this out because it seems to me that the rest of
% the paper is not understandable without reading this section.
% Also, the later sections are equally technical as this one.
% However, I would be happy to put this paragraph back in if you like.
% I don't feel strongly about it.
%
%Now we derive a method for determining the potential gain from
%speculation. The reader not interested in the formal details can
%proceed to the discussions regarding how this method can be used in
%practice, starting in Section~\ref{sec:perfectInfo}.
Using standard notation from microeconomics, let there be $n$
commodities, and let the price vector be ${\mathbf p} = [p_1, p_2,
\ldots, p_n]$, where $p_i$ is the price for good $i$. Let the
resulting allocation for consumers be ${\mathbf x}_i({\mathbf p}) =
[x_{i1}({\mathbf p}), x_{i2}({\mathbf p}), \ldots, x_{in}({\mathbf
p})]^T$, where $x_{ij}$ is consumer $i$'s allocation of good $j$. Let
the initial endowments be ${\mathbf e}_i = [e_{i1}, e_{i2}, \ldots,
e_{in}]^T$, where $e_{ij}$ is consumer $i$'s endowment of good $j$.
Now, consumer $i$'s excess (net) demand of good $j$ is
$z_{ij}({\mathbf p}) = x_{ij}({\mathbf p}) - e_{ij}$. Let
$u_i({\mathbf x}_i)$ be consumer $i$'s utility as a function of its
allocation, and let $\theta_{ih}$ be the fraction of producer $h$ that
consumer $i$ owns. The producers' profits are divided among consumers
according to these shares. However, the consumers are assumed to have
no say-so in the producers' production decisions.
Furthermore, let ${\mathbf y}_i({\mathbf p}) = [y_{i1}({\mathbf p}),
y_{i2}({\mathbf p}), \ldots, y_{in}({\mathbf p})]^T$ be the production
vector of producer $i$, where $y_{ij}$ represents the amount produced,
and a negative number means that the good is an input. Let $Y_i$ be
the production possibilities set of producer $i$. The profit of
producer $i$ is ${\mathbf p} \cdot {\mathbf y}_i({\mathbf p})$, where
${\mathbf y}_i \in Y_i$. For presentation uniformity with the case of
the consumer, we define the excess demand of producer $h$ to be
$z_{hj}({\mathbf p}) = -y_{hj}({\mathbf p})$.
%Note that producers do not have endowments.
%Fredrik: check out the above. Transpose in y-vector. y as a fn of p.
% Definition of producer's excess demand.
Let there be $k$ agents in addition to the speculating agent that we
investigate. The excess demand of these $k$ agents for good $j$ is
\begin{equation}
z_j^k({\mathbf p}) = \sum_{i=1}^k z_{ij}({\mathbf p}).
\label{eq:excessDemandM}
\end{equation}
For the purposes of this section, we do not make any restricting
assumptions about how these $k$ agents make their supply/demand
decisions (which determine the excess demands). In particular, we do
not assume that agents act competitively. The speculating agent that
we investigate uses its information about $z_j^k({\mathbf p})$ as the
basis of its strategic behavior as is now described.
The total excess demand with the speculating agent included is
\begin{equation}
z_j({\mathbf p}) = z_j^k({\mathbf p}) + z_{sj}({\mathbf p}).
\label{eq:excessDemand}
\end{equation}
Once the market has reached a general equilibrium, supply meets
demand, i.e. $z_j({\mathbf p}) = 0$ for every good $j$.~\footnote{This
holds even if agents are strategic---assuming that the particular
market algorithm finds an equilibrium. The equilibrium reflects how
the speculating agent is acting strategically, and how the other
agents have reacted to the new price vector that came about due to the
strategic agent's actions.} Substituting this into
(\ref{eq:excessDemand}) gives
\begin{equation}
z_{sj}({\mathbf p}) + z_{j}^{k}({\mathbf p}) = 0.
\label{eq:marketCleared}
\end{equation}
\subsection{Case A: Speculating Consumer}
%================================================
%Now we express the utility of the speculating consumer as a function
%of ${\mathbf p}$, i.e. $u_s({\mathbf x}_s({\mathbf p}))$. Therefore,
%a...
A solution to the following maximization problem gives the highest
utility that a speculating consumer theoretically can obtain.
\begin{eqnarray}
\label{eq:optimalConsume}
&&\hspace{-0.25in} \max_{{\mathbf p}} \ u_{s}({\mathbf x}_{s}({\mathbf p})) \ \mbox{ s.t. } \\
&&\hspace{-0.25in} x_{sj}({\mathbf p}) \geq 0 \ \mbox{ (consumer does not produce)} \nonumber \\
&&\hspace{-0.25in} x_{sj}({\mathbf p}) = e_{sj} - z_j^k({\mathbf p}) \ \mbox{ (supply meets demand)} \nonumber \\
&&\hspace{-0.25in} {\mathbf p} \cdot {\mathbf z}_s({\mathbf p}) = \sum_{h \in producers} \hspace{-0.15in} \theta_{sh} \ {\mathbf p} \cdot {\mathbf y}_h({\mathbf p}) \ \mbox{ (budget constraint)} \nonumber
\end{eqnarray}
provided that the equilibrium is unique and the market protocol finds
it (this is discussed further in Section~\ref{se:reaching}).
%provided that there exist a $z_{sj}$
%leading to a unique solution of the above problem.
The last equality assumes that either the speculating consumer's
utility does not decrease as the amount of any good is increased in
the consumer's consumption bundle, or the consumer can freely dispose
of any good. Otherwise, ``$=$'' should be changed to ``$\leq$''.
%??? I am not sure that the budget constraint is supposed to be
% there in the above optimization.
%Old comment:
%I talked to Fernando today. He means that in (4) you should maximize
%over p s.t. x>=0 AND supply equals demand for every commodity AND
%each competitive producer maximizes revenue given its prod.poss. set
%given prices as external AND each competitive consumer maximizes its
%utility given its budget constraint given prices as external. I think
%I need to add these extra constraints (which you and I clearly
%understood but did not state) explicitly into definition (4). What do
%you think? The current version of (4) reaches a trivial maximum when
%p = 0 and x = infinity?
\subsection{Case B: Speculating Producer}
%================================================
Similarly to the case of a speculating consumer, a solution to the
following maximization problem gives the highest profit that a
speculating producer can obtain.
\begin{eqnarray}
\label{eq:optimalProduce}
&&\max_{{\mathbf p}} \ {\mathbf p} \cdot {\mathbf y}_s({\mathbf p}) \ \mbox{ s.t. } \\
&&{\mathbf y}_s({\mathbf p}) \in Y_s \ \mbox{ (feasible production plan)} \nonumber \\
&&y_{si} = z_i^k({\mathbf p}) \ \mbox{ (supply meets demand)} \nonumber
\end{eqnarray}
provided that the equilibrium is unique and the market protocol finds
it. The last equality turns into $y_{si} \geq z_i^k({\mathbf p})$ if
free disposal~\cite{Mas-Colell95} for both inputs and outputs is
possible for each commodity.
We call the solution to the applicable optimization problem above
(depending on whether the speculator is a producer or a consumer)
${\mathbf p}^*$.
\section{Strategic Behavior with Perfect Information}
%====================================================
\label{sec:perfectInfo}
In the previous section we obtained a method for determining the
highest utility that an agent theoretically can obtain. This section
shows how this method can be used in practice.
\subsection{A Simple Example}
%============================
%FREDRIK: I HAVE NOT CHECKED THE FORMULAS IN THE DERIVATIONS IN THIS SECTION
To demonstrate the method, we show how it applies to a specific case.
We choose a setting with no producers. In such {\em pure exchange
markets}, the consumers just reallocate their initial endowments among
themselves~\cite{Varian92,Kreps90:Course}.
%
%In pure exchange markets, the prices and consumption decisions are in
%general equilibrium if markets clear (consumption equals endowment for
%each commodity), and each consumer consumes a bundle of commodities
%such that it could not afford another bundle of higher utility given
%its initial endowments and the prices. %???
%Many of the results from pure exchange markets can be easily
%generalized to settings which incorporate
%producers~\cite{Mas-Colell95}.
%
We choose a set of agents that is similar to the one described by Hu
and Wellman~\cite{Hu96:Self}. Specifically, we let every
agent---except for the speculating one that we investigate---be a
competitive agent with constant elasticity of substitution, i.e. a
utility function of the form
\begin{equation}
u_i({\mathbf x}) = \left( \sum_{j=1}^n \alpha_{ij}
x_{ij}^{\rho}\right)^{\frac{1}{\rho}}
\label{eq:CES}
\end{equation}
where we have chosen $\alpha_{ij}=1$ and $\rho = \frac{1}{2}$. Since
these agents act competitively, and the speculating agent is assumed
to have perfect information, the analysis of this example is protocol
independent as long as the resources are reallocated after equilibrium
(\ref{eq:marketCleared}) has been reached.
For simplicity and readability, we use only two goods ($n=2$). The
endowments are the same for all the competitive agents and they are 2
for good 1 and 1 for good 2. We let the speculating agent have the
utility function
\begin{equation}
u_s({\mathbf x}) = \sum_{j=1}^n ln(x_{sj}),
\label{eq:stratUtil}
\end{equation}
and an endowment of 1 for both goods.
Most of this section is devoted to computing the gain from strategic
behavior. For the casual reader, the main results of this section are
condensed in Table~1 and Figure~\ref{fi:utility} below.
We get, e.g. from~\cite{Wellman94} and the definition of excess
demand, that the excess demand of the competitive agents is
\begin{equation}
z_1^k({\mathbf p}) = k \left( \frac{2p_{1}+1}{p_{1}(p_{1}+1)}-2 \right).
\label{eq:compExcessDemand}
\end{equation}
Because prices are only relative, we can set one of the prices
arbitrarily, e.g. $p_n$ can be set to 1, i.e. $p_2=1$. From the
budget constraint
%($\sum_{j=1}^n p_j z_j({\mathbf p}) = 0$)
(${\mathbf p} \cdot {\mathbf z}({\mathbf p}) = 0$) we then get
$z_n({\mathbf p}) = -\sum_{j=1}^{n-1} p_j z_j({\mathbf p})$, i.e.
$z_2^k(p_1) = -p_1 z_1^k(p_1)$. Using these and (\ref{eq:stratUtil})
and (\ref{eq:compExcessDemand}), we get
\begin{equation}
\begin{array}{ll}
u_s({\mathbf x}(p_1)) = & ln \left(1-k \left( \frac{2p_{1}+1}{p_{1}(p_{1}+1)}-2 \right) \right) + \\
& ln \left(1+k \left( \frac{2p_{1}+1}{p_{1}+1}-2p_{1} \right) \right).
\end{array}
\label{eq:specUtility}
\end{equation}
From (\ref{eq:stratUtil}) we see that $x_{sj}$ must be greater than
zero. If the speculating agent chooses to minimize $p_1$, it should
sell as much of $x_1$ as possible and thus, as seen from the
expression for $x_{s1}$ in (\ref{eq:specUtility}), and the requirement
that $x_{s1} > 0$, we have $p_1 > p_1^{min} =
-\frac{1}{2(2k+1)}+\sqrt{\frac{k}{2k+1}+\left(\frac{1}{2(2k+1)}\right)^{2}}$.
Analogous reasoning for $x_{s2}$ shows that $p_1 < p_1^{max} =
\frac{1}{4k}+\sqrt{\frac{1}{2}\left(1-\frac{1}{k}\right)+\left(\frac{1}{4k}\right)^{2}}$. If
$k$ approaches infinity, both $p_1^{min}$ and $p_1^{max}$ approach
$\sqrt{\frac{1}{2}} \approx 0.707$. Therefore, with an
infinite number of agents, the speculator cannot afford to affect the
price in any way.
The first derivative of $u_s$ with respect to $p_1$ is
\begin{equation}
\begin{array}{ll}
\frac{\partial u_{s}}{\partial p_{1}} = \\
\frac{-1}{1-k\left( \frac{2p_{1}+1}{p_{1}(p_{1}+1)}-2\right) }k \left(2\frac{1}{p_{1}(p_{1}+1)}-\frac{2p_{1}+1}{p_{1}^{2}(p_{1}+1)}- \frac{2p_{1}+1}{p_{1}(p_{1}+1)^{2}}\right)+ \\
\frac{1}{1-k\left( \frac{2p_{1}+1}{p_{1}+1}-2p_{1}\right) }k\left( \frac{2}{p+1}-\frac{2p_{1}+1}{(p_{1}+1)^{2}}-2\right).
\end{array}
\label{eq:dudp1}
\end{equation}
%Treating $\frac{\partial u_s}{\partial p_1}$ analytically is not easy,
%if at all possible. Rather it has to be analyzed with a mathematical
%computer software.
It turns out that $\lim_{p_1 \rightarrow p_1^{min+}} \frac{\partial
u_s}{\partial p_1} > 0$ and $\lim_{p_1 \rightarrow p_1^{max-} }
\frac{\partial u_s}{\partial p_1} < 0$, and that the solution to
$\frac{\partial u_s}{\partial p_1} = 0$ is unique in the interval
$p_1^{min} < p_1 < p_1^{max}$. Therefore, the optimum, $p_1^*$, is
obtained by solving $\frac{\partial u_s}{\partial p_1} = 0$.
The results of optimal strategic behavior are compared to the results
of competitive behavior by the same agent. When the agent acts
competitively, the excess demand (with $u_s$) is $z_{s1} =
\frac{p_{1}+1}{2p_{1}} -1$. Setting the excess demand to zero gives
$k \left( \frac{2p_{1}+1}{p_{1}(p_{1}+1)}-2 \right) +
\frac{p_{1}+1}{2p_{1}} -1 = 0$. Solving for the competitive price
gives $p_1^c = \sqrt{\frac{2k+1}{4k+1}}$. The results
are shown in Table~1.~\footnote{Since utility is ordinal, one should
be careful when discussing degrees of improvement.}
\begin{table}[htb]
%\vspace{-0.1in}
{\scriptsize
\begin{center}
\begin{tabular}{||r|r|r|r|r|r|r||} \hline \hline
$k$ & $p_{1}^{min}$ & $p_{1}^{max}$ & $p_{1}^{*}$ & $p_{1}^{c}$ & $u_{s}( p_{1}^{*})$&$u_{s}( p_{1}^{c})$ \\ \hline
1&0.4343&1.281&0.7601&0.7746&1.746&1.626 \\ \hline
2&0.5403&1.000&0.7402&0.7454&2.202&2.152 \\ \hline
5&0.6303&0.8262&0.7227&0.7237&2.614&2.602 \\ \hline
10&0.6667&0.7670&0.7154&0.7157&2.788&2.784 \\ \hline
20&0.6863&0.7372&0.7114&0.7115&2.884&2.884 \\ \hline
30&0.6931&0.7272&0.7100&0.7160&2.918&2.918 \\ \hline
100&0.7029&0.7131&0.7080&0.7080&2.967&2.967 \\
\hline \hline
\end{tabular}
\end{center}
}
%\vspace{-0.17in}
\caption{\em Acting strategically vs. acting competitively. $k$ is the
number of agents acting competitively. $p_1^{min}$ is the price for
$x_1$ in the market when the speculating agent sells as much $x_1$ as
possible. $p_1^{max}$ is the price for $x_1$ in the market when the
speculating agent sells as much $x_2$ as possible. $p_1^*$ is the
market price as a consequence of strategic acting. $p_1^c$ is the
market price as a consequence of competitive acting by the same agent.
The values $u_s$ are the corresponding utilities for the agent under
observation.}
%\vspace{-0.1in}
\end{table}
In Figure~\ref{fi:utility}, the utility is plotted for the situations
where the agent acts strategically and where it acts competitively. As
expected (see e.g.~\cite{Roberts76:Incentives}), the larger the number
of agents, the smaller the gain from strategic behavior, and the less
reason not to act competitively. In this example, already when the
number of competitive agents is around five, the gain from strategic
behavior is negligible.
%-----------------------
\begin{figure}[!hbt]
\epsfxsize=3.6in
\hspace*{\fill}
\epsffile{utility.eps}
\hspace*{\fill}
%\vspace{-0.38in}
\caption{{\it Comparison of strategic and competitive utility,
$u_s(p_1^*)$ and $u_s(p_1^c)$. The horizontal axis shows a number of
interesting values rather than a specific scale. We see that the
larger the number of agents, the smaller the gain from strategic
behavior.}}
\label{fi:utility}
%\vspace{-0.1in}
\end{figure}
%-----------------------
\subsection{Reaching Equilibrium}
%====================================
\label{se:reaching}
%Can this section be made more general, i.e. less specific to walras???
Obviously an agent's best strategy is to declare an excess demand
function such that the market will converge to the prices that are
optimal for the speculating agent. More formally, when perfect
information is available, an agent's best strategy---even if the other
agents are not acting competitively, and some of them may be
producers---is to declare an excess demand function with the property
\begin{equation}
z_{sj}^*({\mathbf p}^*) = -z_j^k({\mathbf p}^*),
\label{eq:strategicDemand}
\end{equation}
for each good $j$, and which has a form such that the particular
algorithm for searching for the market equilibrium converges to
${\mathbf p}^*$. Depending on the setting, the difficulty of finding
such a function varies. As shown below, finding it for the simple
example from above where all other agents' supply/demand functions can
be taken as fixed (to do this, they do not have to be competitive in
general) is normally not hard. However, finding it may be more
difficult if the other agents try to act strategically via speculation
as well. These game theoretic issues will be addressed in
Section~\ref{sec:protocols}.
Having computed the optimal speculative solution, $u_s^*(p_1^*)$, we
would like to describe the strategic behavior leading to this solution
under any particular market protocol used. For example, if $p_1$ is
established via an algorithm whose only requirement for finding the
equilibrium is $\partial z_1(p_1)/\partial p_1 < 0$,~\footnote{An
example of such an algorithm is binary search. The \textsc{Walras}
market framework uses this implementation.} and we have that $\partial
z_1^k(p_1)/\partial p_1 < 0$ (i.e. demand decreases as price
increases---as is the case in our example above), we see that if
\begin{equation}
z_{s1}^*(p_1^*) = -z_1^k(p_1^*) \mbox{ and } \frac{\partial
z_{s1}^*(p_1) }{\partial p_1} \leq 0,
\label{eq:specStrategicDemand}
\end{equation}
%The binary search might take infinitely long???
there is a single solution for $p_1 = p_1^*$, and that solution will
be found by the algorithm.~\footnote{The above reasoning extends
easily to a market with more than two goods. If ${\mathbf p}$ is
established via an algorithm whose only requirements for finding the
equilibrium are $\partial z_i({\mathbf p})/\partial p_i < 0$ and
$\partial z_i({\mathbf p})/\partial p_j \geq 0$, $i \neq j$ (e.g.
\textsc{Walras}), and we have that $\partial z_i^k({\mathbf
p})/\partial p_i < 0$ and $\partial z_i^k({\mathbf p})/\partial p_j
\geq 0$, $i \neq j$, then (\ref{eq:specStrategicDemand}) should be
generalized to $z_{si}^*({\mathbf p}^*) = -z_i^k({\mathbf p}^*)$ and
$\partial z_{si}^*({\mathbf p})/\partial p_i \leq 0$ and $\partial
z_{si}^*({\mathbf p})/\partial p_j \geq 0$, $i \neq j$.}
%
%OLD VERSION OF THE ABOVE FOOTNOTE:
%\footnote{For a market with more than two goods, like the one
%in~\cite{Hu96:Self}, for \textsc{Walras} to be guaranteed to converge,
%(\ref{eq:specStrategicDemand}) must be generalized to
%$z_{si}^*({\mathbf p}^*) = -z_i^k({\mathbf p}^*)$ \emph{and} $\partial
%z_{si}^*({\mathbf p})/\partial p_i \leq 0$ \emph{and} $\partial
%z_{si}^*({\mathbf p})/\partial p_j \geq 0$, $i \neq j$, where the last
%condition guarantees that gross substitution in the market is
%preserved.}
%
It turns out that simple demand revelation strategies exist for the
speculator which guarantee that an equilibrium will be reached where
the speculator's maximal gain from speculation (derived earlier in
this paper) materializes. The following linear function defines one
such strategy---i.e. it fulfills (\ref{eq:specStrategicDemand}):
\begin{equation}
z_{s1}(p_1) = \overline{p_1^*} - \overline{z_1^k(p_1^*)} - p_1,
\label{eq:estDemand}
\end{equation}
where $\overline{z_1^k(p_1^*)}$ and $\overline{p_1^*}$ are the
speculator's (perfect) estimates of $z_1^k(p_1^*)$ and $p_1^*$
respectively. Another viable strategy is defined by the constant
function
\begin{equation}
z_{s1}(p_1) = - \overline{z_1^k(p_1^*)}.
\label{eq:estDemandConst}
\end{equation}
\section{Dealing with Uncertainty: Strategic Behavior under Biased Beliefs about Others}
%======================================================================
\label{sec:uncertainty}
This section extends the discussion to include the impact of
uncertainty on the speculating agent's strategy.
\subsection{The General Setting}
%===============================
Above, when an excess demand function was chosen based on perfect
information, the exact form of the function was unimportant as long as
it fulfilled (\ref{eq:specStrategicDemand}). However, if the
speculating agent cannot estimate $z_1^k$ perfectly, its outcome will
depend on the function chosen, i.e. the choice of an excess demand
function will depend on the probability distribution that
characterizes the uncertainty in the speculator's beliefs. Rather
than analyzing how the excess demand is chosen for different
uncertainty situations and how the speculator should try to reduce the
uncertainty by learning about its environment in an efficient way, we
describe how, for a specific choice of $z_{sj}$, a specific error in
the estimation of the competitive agents' behavior affects the outcome
of the market.
Independently of how the $z_{sj}$ function is chosen, the possible
market outcomes can be determined by solving
(\ref{eq:marketCleared}). If no solution exists, of course, no
algorithm can find it, and if multiple equilibria exist, a protocol
dependent analysis is required to find out which one will be chosen.
\subsection{The Example Revisited}
%=================================
%FREDRIK: I HAVE NOT CHECKED THE FORMULAS IN THE DERIVATIONS IN THIS SECTION
Returning to the above example, we first assume that $z_{s1}$ has been
chosen as describe by (\ref{eq:estDemand}), but that now there is an
error in the estimation. We define this error through\footnote{If the
speculating agent can learn about the other agents and change its
excess demand during the market process, the error might decrease
during this process. The error described here is the error remaining
when the process terminates.}
\begin{equation}
\overline{p_1^*}-\overline{z_1^k(p_1^*)} = (1+e)(p_1^* - z_1^k(p_1^*)).
\label{eq:errDef}
\end{equation}
Provided that the speculator stops learning about $z_1^k(p_1)$ at some
point in time, and hereby fixes $z_{s1}(p_1)$, any market protocol
whose only requirement for finding the equilibrium is that $\partial
z_1(p_1)/\partial p_1 < 0$ (e.g. the binary search used in
\textsc{Walras}) is guaranteed to converge independently of how large
the estimation error is, since (\ref{eq:specStrategicDemand}) is
satisfied. Inserting the expressions from
(\ref{eq:compExcessDemand}), (\ref{eq:estDemand}), and
(\ref{eq:errDef}) in (\ref{eq:marketCleared}) gives
\begin{equation}
\begin{array}{ll}
(1+e)\left( p_{1}^{*}-k \left( \frac{2p_{1}^{*}+1}{p_{1}^*(p_{1}^{*}+1)}-2 \right) \right) - p_{1} + \\
k \left( \frac{2p_{1}+1}{p_{1}(p_{1}+1)}-2 \right) = 0.
\end{array}
\label{eq:estEquil}
\end{equation}
This equation was solved for different errors $e$, and different
numbers of competitive agents $k$. The corresponding
utilities---normalized to the utility that would result from
competitive behavior---are plotted in Figure~\ref{fi:err2}.
%-----------------------
\begin{figure}[!hbt]
%\vspace{-0.1in}
\epsfxsize=3.6in
\hspace*{\fill}
\epsffile{err2.eps}
\hspace*{\fill}
%\vspace{-0.4in}
\caption{{\it The utility as a function of the estimation error. $k$
is the number of competitive agents.}}
\label{fi:err2}
%\vspace{-0.1in}
\end{figure}
%-----------------------
As seen from Figure~\ref{fi:err2}, when the number of agents is small,
the gain from speculating is large; even when there is an error
involved, it often pays off to speculate. But as the number of agents
increases, acting competitively is close to acting strategically with
perfect information, and it is worse to speculate, even with
surprisingly small errors. The break even points for $1$, $2$, $5$,
$20$, and $100$ agents are at an estimation error of approximately
$\pm 5$\%, $\pm 3$\%, $\pm 1$\%, $\pm 0.4$\%, and $\pm 0.05$\%
respectively. Looking the other way around, with $100$ competitive
agents and a $\pm 5$\% error (the break even error for $1$ competitive
agent), the loss compared to acting competitively is substantial.
\section{Strategic Behavior by Multiple Agents}
%==============================================
\label{sec:protocols}
%From Fredrik's email: ???
%What we really try to say, looking back at e.g. eq. (4), is that z^{k}
%can change as we change z_{s}, and that there for certain situations
%is not possible to find a stable pair z_{s}, z^{k}. This kind of
%reasoning should probably also be included in section 2 in some way.
%Be careful that the references separated by hyphens are correct in the
%following after you move sections around. ???
In our simple example, only one agent was speculating and the others
were acting competitively. Even though
(\ref{eq:excessDemandM})--(\ref{eq:optimalProduce}) and
(\ref{eq:strategicDemand})--(\ref{eq:errDef}) are valid even in the
case where every agent is speculating, determining market outcomes in
a protocol independent way is not possible in such settings in
general. The reason is that an agent cannot treat others' strategies
(e.g. policies for revealing excess supply/demand {\em functions}) as
fixed because the others would like to tailor their strategies to the
specific strategy that the agent chooses. The strategies are in {\em
Nash equilibrium}~\cite{Nash50:Eq,Mas-Colell95,Kreps90:Course} if each
agent's strategy is its best response to the others' strategies. This
can be viewed as a necessary condition for system stability in
settings where all agents act strategically.~\footnote{A stronger
condition of stability is to require incentive compatibility,
i.e. that an agent's strategy is optimal (for the agent) no matter
what strategies others choose. Market protocols have been studied
using this solution concept in~\cite{Barbera95:Strategy}.} In
sequential protocols, one can also strengthen the Nash equilibrium
solution concept in multiple ways by requiring that the strategies
stay in equilibrium at every step of the
game~\cite{Mas-Colell95,Kreps90:Course}. Unlike our analysis, the
Nash equilibrium outcome is specific to the market protocol.
Important factors impacting the outcome are the order in which bids
are submitted (see e.g. Stackleberg vs. Cournot
models~\cite{Mas-Colell95}), whether the bids are sealed or
open~\cite{Sandholm96:Vickrey}, whether the protocol is iterative (the
agents can change their excess demand between iterations) or not,
whether the agents can decommit from their agreements by paying a
penalty~\cite{Sandholm96:Leveled}, {\em etc}.
In some games, no Nash equilibrium exists in pure (non-randomized)
strategies. The following simple example illustrates this. Let there
be two consumer agents, A and B, that engage in a market where they
reveal their excess demand functions simultaneously and in a single
round. Agent A can choose between two strategies (A1 and A2), and B
can choose between B1 and B2. Provided that A knows that B will
choose B1, A will choose A2, and A1 if B chooses B2. Provided that B
knows that A will choose A2, B will choose B2, and B1 if A chooses A1.
Now, from every possible pair of strategies, one agent would be
motivated to deviate to another strategy, i.e. no Nash equilibrium
exists.
%Now there is no solution to (\ref{eq:marketCleared}) and
%(\ref{eq:optimalConsume}), and therefore the outcome is heavily
%dependent on the protocol used.
In general, existence and uniqueness of a general equilibrium (where
agents act competitively) for a market does not imply existence and
uniqueness of a Nash equilibrium (or an individually rational
non-cooperative equilibrium~\cite{Malinvaud85:Lectures}).
%Whereas game theoretic aspects of trades of a single item have been
%thoroughly examined, both in economics and in AI (see
%e.g. \cite{Rosenschein94:Rules,Sandholm96:Vickrey}), the lack of game
%theoretic analysis of equilibrium markets is striking, especially in
%AI.
We argue that for each protocol proposed for implementation of
equilibrium markets including self-interested computational agents, a
thorough game theoretic analysis should be
attempted~\cite{Sandholm96:Leveled,Sandholm96:Vickrey,Rosenschein94:Rules}.
However, as discussed above, some games lack a Nash equilibrium, or it
may not be unique. In addition, some protocols are hard to analyze
game theoretically. For example, in \textsc{Walras}, the agents might
change their demand functions during the computation of the
equilibrium. Then some agents may deliberately send false bids to
generate more iterations of the market process in order to learn more
about other agents' excess demand/supply functions. If many agents are
involved in such probing, it seems that time becomes an important
factor. Some agents might reveal progressively more of their
competitive demands in order to speed up the convergence (as it might
be urgent for them to get the resources traded), while others might
extend the probing in order to maximize their benefit from the
trade.~\footnote{Some work has addressed non-competitive behavior in
\textsc{Walras}~\cite{Hu96:Self}, although there was only one
speculating agent in the experiments, and this agent was limited to
simple linear price prediction about how its actions affect the
prices.
%%Furthermore, the work has more a flavor of indirect utility
%%improvement through prediction of prices, rather than the type of
%%direct approach to utility maximization from estimation of other
%%agents' excess demands described in this paper.
%Furthermore, that work used indirect utility improvement via
%estimating the agent's impact on prices, as opposed to our direct
%approach to utility maximization based on estimated excess demands of
%the other agents.
Further analysis is required to determine whether its optimal strategy
can be captured in this model. This need not be the case because the
optimal strategy may involve some more ``aggressive'' behavior,
e.g. the probing described above.}
%??? Common knowledg assumptions in Nash, but not dominant strat.
%Way of tying in Econometrica?
Once the other agents' strategies are known (e.g. from a game
theoretic equilibrium analysis), the methods of this paper can be used
to analyze the speculating agent's strategy alternatives. The methods
are protocol independent, and they can be used to estimate the
potential gains from speculation in any particular setting, as well as
to determine how far from the optimal strategy a particular strategy
is---as long as the other agents' strategies can be fixed
conceptually. This does not mean that they need to be known with
certainty.
The methods of this paper can also be used when game theoretic
analysis fails. Especially when speculation is based on expected
actions of other agents---instead of a game theoretic equilibrium
analysis of strategies---the theory of speculation under biased
beliefs is highly applicable. In addition, the example market used in
this paper suggests that if a market is of at least moderate size,
%and the agents submit their entire excess demand/supply functions
%simultaneously,
the gain from speculation is so small, and the risk of being
significantly worse off due to estimation error is so great, that one
can expect that each agent will act close to its competitive behavior.
%And thus existence of a unique competitive equilibrium can be
%sufficient. On the other hand, agents might want to submit bids that
%lead to convergence of the market if they will be better off after the
%trade, and fail otherwise. This makes the analysis even harder.
\section{Conclusions}
%====================
\label{sec:conclusions}
We presented a method for computing the maximal advantage of
speculative strategic behavior in general equilibrium based markets.
It is computed from the other agents' supply/demand functions (classic
competitive behavior by the other agents is a special case of this).
The method enables one to analyze how much an agent could gain or lose
by speculating in a particular system, and it is also useful when
evaluating different strategies since it allows one to determine how
close to the optimal strategy they are. Our analysis is valid for a
wide variety of known market protocols. We also constructed demand
revelation strategies that guarantee that an agent can drive the
market to an equilibrium where the agent's maximal advantage from
speculation materializes.
Our study of a particular market shows that as the number of agents
increases, the gains from speculation decrease---often turning
negligible already at moderate numbers of agents. The study also
shows that under uncertainty regarding other agents, competitive
acting is often close to optimal, while speculation can make the agent
significantly worse off---even if the agent's beliefs are just
slightly biased.
We believe that computational agents representing self-interested real
world parties will deviate from competitive behavior in practice only
if the potential gain from speculation is sufficiently large compared
to the cost of the computation or information gathering actions
required for speculation. We also believe that an agent will not
speculate when that incurs potentially large losses when estimation
errors are present. Merging the above results with these beliefs
suggests that speculation problems diminish as the market grows or the
agents' information about others becomes less certain.
Finally, we discussed the protocol dependent game theoretic issues
related to multiple agents counterspeculating. There are many open
issues in this area and the difficulties should not be underestimated.
%In conclusion we argue that even though we believe the contribution of
%this paper to be a very important step towards equilibrium markets
%including self-interested agents, it is at the same time a quite small
%one, and a lot of research remains to be done.
\section*{Acknowledgments}
%=========================
%This might be excluded if there is not space enough:
The authors thank Arne Andersson, Junling Hu, John Nachbar, Eric
Schenk, Fernando Tohm\'e, Michael Wellman, and Curt Wells for
interesting discussions and comments. Fredrik also thanks Hans
Akkermans, Rune Gustavsson and Hans Ottosson for all their support.
%Tuomas thanks John Nachbar and Fernando Tohm\'e for helpful
%discussions. Fredrik thanks Hans Akkermans, Rune Gustavsson and Hans
%Ottosson for all their support. He also thanks Arne Andersson, Curt
%Wells and Eric Schenk for discussions important for the creation of
%this paper.
%How about acknowledging the comments of Wellman and Hu ???
%For compilation at Fredrik's site:
{\footnotesize
\bibliographystyle{named}
\bibliography{tuomas}
}
%For compilation at Tuomas' site:
%{\tiny
%\bibliography{$HOME/refs/dairefs}
%\bibliographystyle{abbrv}
%}
%\bibliographystyle{$HOME/sty/named}
%\bibliography{tuomas}
\end{document}