%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% scjair.tex
%
% Journal submission of comprehensive supply chain/task allocation
% work to date.
%
% $Id: scjair.tex,v 1.40 2003/11/11 19:12:26 wwalsh1 Exp $
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[twoside,11pt]{article}
\usepackage{jair}
\usepackage{theapa}

% \input epsf

\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsmath}
\usepackage{url}
\usepackage{mathptm}
\usepackage{longtable}

% Fill in per JAIR editor specs
\jairheading{19}{2003}{513-567}{1/03}{11/03}
\ShortHeadings{Decentralized Supply Chain Formation}
{Walsh \& Wellman}
 \firstpageno{513}

\newsavebox{\rcsdate}
\begin{lrbox}{\rcsdate}
%\tiny
\verb+$Date: 2003/11/11 19:12:26 $+
\end{lrbox}

\newsavebox{\rcsid}
\begin{lrbox}{\rcsid}
%\tiny
\verb+$Id: scjair.tex,v 1.40 2003/11/11 19:12:26 wwalsh1 Exp $+
\end{lrbox}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Generally useful macros.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Kluwer publishing style
%\newtheorem{conjecture}{Conjecture}[chapter]

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}{Definition}
% \newtheorem{example}[theorem]{Example}
\newtheorem{observation}[theorem]{Observation}
% \newtheorem{proposition}[theorem]{Proposition}

\newenvironment{proof}{\emph{Proof.}}{\proved}

\newenvironment{copytheorem}[2]{\noindent \\ \textbf{Theorem~#1} \textit{#2}}
{\\ \\}

% Such that
\newcommand{\st}{\mbox{ s.t. }}

\newcommand{\proved}{\ensuremath{\Box} \smallskip}
\newcommand{\dollar}[1]{\${#1}}

% Font for code.
\newcommand{\code}{\texttt}

% Font for a good or agent name.
\newcommand{\name}[1]{\textsf{#1}}

\newcommand{\netname}[1]{\textsc{\name{#1}}}

% A definition.
\newcommand{\defn}[1]{\textbf{\textit{#1}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Document-specific macros.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\askPrice}[1]{\ensuremath{\alpha(#1)}}
\newcommand{\bidPrice}[1]{\ensuremath{\beta(#1)}}



\newcommand{\network}{\ensuremath{(V,E)}}
\newcommand{\allocPrime}{\ensuremath{(V',E')}}
\newcommand{\allocStar}{\ensuremath{(V^*,E^*)}}
\newcommand{\allocHat}{\ensuremath{(\hat{V},\hat{E})}}
\newcommand{\netHat}{\ensuremath{(\hat{V},\hat{E})}}

\newcommand{\Tasks}{\ensuremath{G}}
\newcommand{\task}{\ensuremath{g}}
\newcommand{\consGood}{\ensuremath{g_{c}}}
\newcommand{\cost}[1]{\ensuremath{\mbox{\it cost\/}(#1)}}

\newcommand{\solnValue}[1]{\ensuremath{\mbox{value}(#1)}}
\newcommand{\price}[1]{\ensuremath{p(#1)}}
\newcommand{\lbp}[1]{\ensuremath{p_{-}(#1)}}
\newcommand{\ubp}[1]{\ensuremath{p^{-}(#1)}}
\newcommand{\hatPrice}[1]{\ensuremath{\hat{p}(#1)}}
\newcommand{\prices}{\ensuremath{p}}

% Arg1 is the agent, arg2 is the good.
\newcommand{\perCost}[2]{\ensuremath{\hat{p}_{#1}(#2)}}

\newcommand{\edge}[2]{\ensuremath{ \langle #1 , #2 \rangle }}

% Arg1 is agent, arg2 is good.
\newcommand{\agentGoodValue}[2]{\ensuremath{v_{#1}(#2)}}
% Arg 1 is agent, arg2 is allocation.
\newcommand{\agentAllocValue}[2]{\ensuremath{v_{#1}(#2)}}
\newcommand{\agentValue}[1]{\ensuremath{v_{#1}}}


% Arg1 is agent, arg2 is good.
\newcommand{\agentGoodCost}[2]{\ensuremath{\kappa_{#1}(#2)}}
% Arg 1 is agent, arg2 is allocation.
\newcommand{\agentAllocCost}[2]{\ensuremath{\kappa_{#1}(#2)}}
\newcommand{\agentCost}[1]{\ensuremath{\kappa_{#1}}}

\newcommand{\buyInc}{\ensuremath{\delta_b}}
\newcommand{\sellInc}{\ensuremath{\delta_s}}
% Arg 1 is agent, arg 2 is good.
\newcommand{\askDiff}[2]{\ensuremath{\lambda_{#1}^{#2}}}
% Arg 1 is producer.
\newcommand{\prodError}[1]{\ensuremath{\sum_{\edge{g}{#1} \in
         E}\askDiff{#1}{g}+\sellInc}}
\newcommand{\consError}{\ensuremath{\buyInc}}

\newcommand{\numIns}[1]{\ensuremath{N_#1}}

\newcommand{\econError}{\ensuremath{\sum_{\pi \in
       \Pi}[\prodError{\pi}] + |C|\buyInc}}

\newcommand{\sampsbError}{\ensuremath{\sum_{\pi \in
       \Pi}[\sum_{\edge{g}{\pi} \in E} \buyInc + \sellInc] + |C|\buyInc}}

% Arg1= agent, Arg2= allocation, Arg3= prices
\newcommand{\surplus}[3]{\ensuremath{\sigma(#1, #2, #3)}}

%  Arg 1 is the agent, arg2 is the prices
\newcommand{\maxSurplus}[2]{\ensuremath{H_{#1}(#2)}}

\newcommand{\sampsb}{\mbox{SAMP-SB}}
\newcommand{\sampsbd}{\mbox{SAMP-SB-D}}

\newcommand{\ld}{\ensuremath{\lambda \mbox{-} \delta}}

\newcommand{\ask}[1]{\ensuremath{\alpha(#1)}}

% Arg1 = agent, Arg2 = good
\newcommand{\bid}[2]{\ensuremath{\beta(#1,#2)}}

% Arg 1 is agent, arg 2 is good
\newcommand{\win}[2]{\ensuremath{w_{#1}(#2)}}


\begin{document}


%\affil{Artificial Intelligence Laboratory, University of
%Michigan, 1101 Beal Avenue, Ann Arbor, MI 48109-2110, USA}

\title{Decentralized Supply Chain Formation: A Market Protocol and Competitive
  Equilibrium Analysis}
\author{\name William E. Walsh \email wwalsh1@us.ibm.com \\
  \addr  IBM T.\@ J. Watson Research Center \\
  19 Skyline Drive \\
  Hawthorne, NY \ 10532 \ USA \\
  \AND
  \name  Michael P. Wellman \email wellman@umich.edu \\
  \addr
  University of Michigan AI Laboratory \\
  1101 Beal Avenue \\
  Ann Arbor, MI \ 48109-2110 \ USA}

\maketitle


\begin{abstract}
Supply chain formation is the process of determining the structure and
terms of exchange relationships to enable a multilevel, multiagent
production activity.  We present a simple model of supply chains,
highlighting two characteristic features: hierarchical subtask decomposition,
and resource contention.  To decentralize the formation process, we
introduce a market price system over the resources produced along the
chain.  In a competitive equilibrium for this system, agents
choose locally optimal allocations with respect to prices, and outcomes are
optimal overall.  To determine prices, we define a market protocol
based on distributed, progressive auctions, and myopic, non-strategic agent
bidding policies.  In the presence of resource contention, this
protocol produces better solutions than the greedy protocols common in
the artificial intelligence and multiagent systems literature.  The
protocol often converges to high-value supply chains, and when
competitive equilibria exist, typically to approximate competitive
equilibria.  However, complementarities in agent production
technologies can cause the protocol to wastefully allocate inputs to
agents that do not produce their outputs.  A subsequent decommitment
phase recovers a significant fraction of the lost surplus.
\end{abstract}


\section{Introduction}
\label{sec:introduction}

Electronic commerce technology can provide significant improvements
in existing modes of commercial interaction, through increased speed,
convenience, quality, and reduced costs.  Yet some
have proposed more radical visions of how business may be transformed.
Exponential increases in communications bandwidth and computational
ability have the potential to qualitatively decrease the friction in
business interactions.  With this as a premise, Malone and
Laubaucher's treatise on the emerging ``E-Lance
Economy''~\citeyear{Malone98} puts forth the view that, in the
not-too-distant future, business relationships will lose much of their
current persistent character.  Indeed, Malone and Laubaucher propose
that large companies as we know them will cease to exist, and rather
be dynamically formed by ``electronically connected freelancers''
(e-lancers) for the purpose of producing particular goods and
services, and then dissolved when projects are completed.
Others employ the evocative term ``virtual corporation''~\shortcite{Davidow92}
to describe groups of agile organizations
forming temporary confederations for ad hoc purposes.

Whether or not one accepts the full extent of this vision of virtual
corporations, several business trends provide evidence
that we are moving in this direction.
% That high-quality software such
% as the Linux operating system and various Gnu Tools have been
% developed by confederations of freelance hackers provides positive
% evidence for the viability of bottom-up teamwork.  Although there
% has been debate about the general applicability of this freeware
% development model, we can see the trend to virtual corporations
% manifesting more broadly.
Software companies are time-shifting
development between the U.S. and India, and Sun Microsystems now
allows freelance programmers to bid to fix customers' software
problems~\shortcite{Borenstein01}.  Large, traditional manufacturing
companies, exemplified by major automotive manufacturers, increasingly
outsource the production of various components.  Ford and General
Motors (GM) have spun off parts manufacturing into separate
companies~\shortcite{Lucking-Reiley01}.  Start-ups and other small companies
form partnerships to compete with larger, more established companies.
Application service providers supplant in-house provision of standard
operations, information, and technology services.

We study this phenomenon in the guise of supply chains, a common form
of coordinated commercial interaction.  For our purposes, a
\defn{supply chain} is a network of
production and exchange relationships that spans multiple levels of
production or task decomposition.  Whenever we have a producer that
buys inputs and sells outputs, we have a supply
chain.  Although typically used to refer to multi-business structures
in manufacturing industries, any service or contracting relationship
that spans multiple levels can be viewed as a supply chain.

\defn{Supply chain formation} is the process of determining the
participants in the supply chain, who will exchange what with whom,
and the terms of the exchanges.  Traditionally, supply chains have
been formed and maintained over long periods of time by means of
extensive human interactions.  But the
acceleration of commercial decision making is creating a need for more advanced
support.  Companies ranging from
auto makers to computer manufacturers are basing their business models
on rapid development, build-to-order, and customized products to
satisfy ever-changing consumer demand.  And fluctuations in resource
costs and availability mean that companies must respond rapidly to
maintain production capabilities and profits.  As these changes
increasingly occur at speeds, scales, and complexity unmanageable by
humans, the need for automated supply chain formation becomes acute.

Because the agents are autonomous in an electronic commerce setting,
we must generally assume that they have specialized knowledge about
their own capabilities but limited knowledge about other individuals
and the large-scale structure of the problem.  Because agents are
self-interested, they will participate with the goal of maximizing
their own benefit.  Additionally, we may have cause to control the
allocation of each resource individually if, for instance, global
optimization is infeasible or if no one entity has global allocative
authority.  For such environments where information, decision making,
and control are inherently decentralized, we seek to engineer the
process of bottom-up supply chain formation.  This problem is
complicated if the structure of resource contention precludes the use
of simple greedy allocation strategies.

We present a decentralized, asynchronous market protocol for supply
chain formation under conditions of resource scarcity.  The protocol
allows agents to negotiate the formation of supply chains in a
bottom-up fashion, requiring only local knowledge and communication.
In the market protocol, agents' decisions are coordinated by the price
system, with the price for each resource determined through an ascending
auction.

% Experience with market protocols bears evidence that they perform
% predictably and effectively in convex
% domains~\shortcite{Mullen95,Wellman93d,Wellman95a,Ygge98b}, characterized by
% infinite divisibility of resources and nonincreasing returns to scale.
% However, many important resource allocation problems---such as supply
% chain formation---may involve discrete resources, violating the
% standard general conditions for market effectiveness.
% % \footnote{It
% %   should not be surprising that discrete goods complicate matters,
% %   considering the relative difficulties of solving integer programming
% %   as compared to linear programming problems.  Bikhchandani and Mamer
% %   use the correspondence between these constrained optimization
% %   problems to characterize the conditions under which a given discrete
% %   problem will be problematic for a market~\shortcite{Bikhchandani97}.}
% Within economics, protocols for allocation of discrete goods have been
% studied under the heading of auction theory.
%
% Although much of the auction literature focuses on the allocation of
% single items~\shortcite{Friedman93,McAfee87,Vickrey61}, several studies
% address the more challenging problem of allocating multiple related
% items~\shortcite{Demange86,Grether89,Gul97a,Kelso82,Milgrom00,Shapley72}.
% The enormous popularity of eBay~\shortcite{Ebay} and other online consumer
% auctions, and the development of business-to-business auction markets
% by~\shortcite{Covisint} and others has manifested the significance of
% auctions for electronic commerce and has spurred interest in studying
% their properties in environments with complex resource dependencies.

The remainder of the paper describes our market protocol, and characterizes
its behavior theoretically and empirically.\footnote{Further details may be
  found in the first author's dissertation~\shortcite{Walsh01a}.}  We begin in
Section~\ref{sec:supp-chain-problem} with a formal definition of the supply
chain formation problem, and an illustrating application to the automotive
industry.  In Section~\ref{sec:resource-cont-prob}, we show how typical greedy
top-down approaches to supply chain formation can fail in the presence of
resource contention.  We define a price system and analyze static properties
of price equilibria in Section~\ref{sec:price-systems}.  In
Section~\ref{sec:samp-sb-protocol}, we introduce a price-based market protocol
for supply chain formation and analyze its convergence properties.  We present
the results of an empirical study of the protocol in
Section~\ref{sec:experiments}.  In Section~\ref{sec:related-work}, we discuss
relevant results and issues in price-based analysis and auction theory, as
well as some related work in supply chain formation.  We conclude in
Section~\ref{sec:future-work} and suggest extensions and future work.
Throughout, we defer proofs to Appendix~\ref{sec:proofs}. 
% The
% proofs for all theorems are provided in a separate appendix titled
% ``Decentralized Supply Chain Formation: Appendix with Proofs''.

\section{The Supply Chain Formation Problem}
\label{sec:supp-chain-problem}

Agents in the supply chain are characterized in terms of their capabilities to
perform tasks, and their interests in having tasks accomplished.  A central
feature of our model of the problem is \defn{hierarchical task decomposition}:
in order to perform a particular task, an agent may need to achieve some
subtasks, which may be delegated to other agents.  These may in turn have
subtasks that may be delegated, forming a supply chain through a decomposition
of task achievement.  Constraints on the task assignment arise from resource
contention, where agents require a common resource (e.g., a task achievement,
or something tangible such as a piece of equipment) to accomplish their tasks.

Tasks are performed on behalf of particular agents; if two agents need
a task then it would have to be performed twice to satisfy them
both.  In this way, tasks are the same as any other discrete, rival
resource.  Hence, we make no distinction in our model, and use the term
``good'' to refer to any task or resource provided or needed by
agents.  The assumption that goods cannot be shared or reused (i.e.,
have limited available quantities) is necessary for much of our analysis.
Goods that can be replicated at
little or no marginal cost, such as software and information, provide
many interesting challenges to economic analysis~\shortcite{Shapiro99}, not
addressed in this work.

\subsection{Example: Automotive Supply Chain Formation}
\label{sec:auto-example}

We illustrate our model of supply chain formation with an application to a
stylized, hypothetical example from the automotive industry.  Traditionally,
automotive supply chains span many tiers, formed and maintained over long
periods of time through extensive human negotiations.  Some automation is
emerging, for example through
Covisint\footnote{\url{http://www.covisint.com}}, a company formed by GM,
Ford, and DaimlerChrysler to mediate the negotiation and exchange of parts, as
well as other supply chain interactions.  Currently the focus in such efforts
is on a particular exchange relationship within a single level of production.
We consider the broader problem of assembling combinations of relationships
across multiple levels to form complete, feasible supply chains.


\begin{figure}[htbp]
\centerline{\resizebox{5in}{!}{\includegraphics{Graphics/auto-chain-pics.eps}}}
\caption{An automotive supply chain formation problem.}
\label{fig:auto-chain-pics}
\end{figure}

In the example presented in Figure~\ref{fig:auto-chain-pics}, Ford and
GM need to acquire contracts for transmissions in order to produce
particular models of cars.  Ford can produce the transmissions in its
own factories or acquire them from an independent transmission
producer.  GM currently does not have the capacity to produce the
desired transmissions, and must outsource.
The independent transmission producer has capacity to provide
transmissions to either Ford or GM, but not both.  Ford and the
independent factory both require the services of a job
shop for metal-working tasks, but the job shop does not have
capacity to serve them simultaneously.  Contracts with the job shop
and with the two transmission factories are the scarce goods to be
allocated.

The limited capacity of the job shop entails certain constraints on
feasible supply chains.  Ford cannot acquire transmissions from the
independent factory, because the job shop cannot serve the independent
factory and Ford simultaneously.  Additionally, Ford and GM cannot
simultaneously be satisfied.

% In a more realistic scenario, the job shop and independent
% transmission factory are not ``used up'' when they are allocated, but
% rather are constrained to provide service to a limited number of
% agents within a given period of time.  We further discuss temporal
% resources and other modeling issues in
% Section~\ref{sec:modeling-issues}.

\subsection{Problem Specification}
\label{sec:formal-specification}

We provide a formal description of the supply chain formation problem
in terms of bipartite graphs.  The two types of nodes represent goods
and agents, respectively.  A \defn{task dependency network} is a
directed, acyclic graph, $(V, E)$, with vertices $V = G \cup A$,
where:
\begin{eqnarray*}
G & = & \mbox{the set of goods}, \\
A & = & C \cup \Pi \mbox{, the set of agents}, \\
C & = & \mbox{the set of consumers}, \\
\Pi & = & \mbox{the set of  producers},
\end{eqnarray*}
and a set of edges $E$ connecting agents with goods they can use or
produce.  There exists an edge \edge{g}{a} from $g \in G$ to $a\in A$
when agent $a$ can make use of one unit of $g$, and an edge
$\edge{a}{g}$ when $a$ can provide one unit of $g$.  If an agent
requires multiple units of a good as input, then we treat each unit as a
separate edge, distinguishing them by subscripts.  (Edges without
explicit subscripts are interpreted as implicitly subscripted by
``1''.)  For instance, if agent $a$ requires two units of $g$ as
input, then its input edges are $\edge{g}{a}_1$ and $\edge{g}{a}_2$.
% We treat multiple output units in the same manner.
% Both inputs and outputs must be expressed in integer quantities.

The various agent types are characterized by their position in the
task dependency network.  Each \defn{consumer}, $c \in C$, wishes to
acquire one
unit of one good from its set of consumable goods, $G_c \subseteq G$,
where $\edge{g}{c} \in E$ iff $g \in G_c$.

A \defn{producer} can produce a single unit of an \defn{output} good
conditional on acquiring some \defn{input} goods.  With each producer
$\pi \in \Pi$ we associate:
\begin{enumerate}
\item an input set, $I_\pi \subseteq G$, such that $g \in I_\pi$
iff there are edges $\edge{g}{\pi}_k \in E$ for one or more $k$, and
\item a single output, $g_\pi \in G \setminus I_\pi$, such
that $\edge{\pi}{g_\pi} \in E$.
\end{enumerate}

A producer's input goods are \defn{complementary} in that the agent
must acquire all of them in order to produce its output; it cannot
accomplish anything with only a partial set.  Alternate producers with
the same output indicate different ways that a good can be produced.

%A \defn{supplier} can supply some set of goods, up to some maximum
%quantity for each, without requiring any input goods:
%\begin{quote}
%For each supplier $s$, there there exists a set $G_s \subseteq G$,
%such that for each $g \in G_s$ there exist edges $\edge{s}{g}_k \in E$
%for one or more $k$.
%\end{quote}

Task dependency networks are constrained to be acyclic, that is, no
agent produces goods that could be used to assemble its inputs through
any chain of production.
% This restriction enables some of the
% analytic results we describe in subsequent sections.
Although we might
broadly view all global commerce as one large cycle of production and
consumption, in practice, negotiations tend to be clustered within
more limited scopes of concern, often referred to as ``industries''.
The resulting supply chains are typically acyclic.

\begin{figure}
\centerline{\resizebox{5in}{!}{\rotatebox{270}{\includegraphics{Graphics/auto-network.eps}}}}
\caption{Network \netname{auto}: A task dependency network for
the automotive supply chain depicted in
Figure~\ref{fig:auto-chain-pics}.}
\label{fig:auto-network}
\end{figure}

Figure~\ref{fig:auto-network} shows an example task dependency network
for the automotive supply chain problem of
Figure~\ref{fig:auto-chain-pics}.  Here the goods are indicated by
circles, and agents by boxes.  Producers with inputs are represented by
curved boxes.  The
numbers under agent boxes represent production costs and consumption values,
explained below.
% Costs and values are indicated under the agents.
An arrow from an agent to a good indicates that the agent can provide
that good, and an arrow from a good to an agent indicates that the
agent can make use of the good.  For instance, the producer labeled
Ford Auto Assembly requires Worked Metal and
Ford Transmissions in order to produce cars.  Since the transmissions
produced by the Ford Transmission Factory can be used only by Ford,
we need to distinguish Ford and GM transmissions as separate goods.
This in turn requires that we introduce Ford and GM Transmission
Subcontractor producers to model the fact that the Independent
Transmission Factory can be used to produce either type.

An \defn{allocation} is a subgraph $(V',E') \subseteq (V,E)$.  For $a
\in A$ and $g \in G$, an edge $\edge{a}{g} \in E'$ means that agent
$a$ provides $g$, and $\edge{g}{a} \in E'$ means $a$ acquires $g$.
% For convenience, We use the indicator function $\win{e}{E'}$ to
% indicate that $e \in E'$.
An allocation's vertices are the agents and goods incident on its
edges:
\begin{enumerate}

\item An agent is in an allocation graph iff it acquires or provides a
good:
\begin{quote}
For $a \in A$, we have $a \in V'$ iff $\edge{g}{a} \in E'$ or
$\edge{a}{g} \in E'$.
\end{quote}

\item A good is in an allocation graph iff it is acquired or provided:
\begin{quote}
For $g \in G$, we have $g \in V'$ iff $\edge{g}{a} \in E'$ or
$\edge{a}{g} \in E'$.
\end{quote}

\end{enumerate}

A producer $\pi$ is \defn{active} iff it provides its output.  A
\defn{producer is feasible} iff it is inactive or acquires all its
inputs.  Consumers are always feasible.

Good $g$ is in \defn{material balance} in $\allocPrime$ iff the number
of edges in equals the number out:
\[
\left| \{(a,k) \:|\: \edge{a}{g}_{k} \in E'\}\right| =
\left| \{(a,k) \:|\: \edge{g}{a}_{k} \in E'\}\right|.
\]

An \defn{allocation is feasible} iff all agents are feasible and all goods
are in material balance.  A \defn{solution} is a feasible
allocation that forms a partial ordering of feasible production,
culminating in consumption.  That is, some consumer acquires a good it
desires:
\begin{quote}
There exists a $\edge{g}{c} \in E'$ such that $c \in C \cap V'$.
\end{quote}
A solution may involve multiple consumers.  If consumer $c$ is in a
solution $\allocPrime$ then we say that $\allocPrime$ is a
\defn{solution for $c$}.


%If negotiation resulted in such a production cycle, there would be no
%way to execute the transaction sequence.

\begin{figure}

\centerline{\resizebox{5in}{!}{\rotatebox{270}{\includegraphics{Graphics/auto-solution.eps}}}}
\caption{A solution to Network \netname{auto}.}
\label{fig:auto-solution}
\end{figure}

Figure~\ref{fig:auto-solution} shows a solution allocation for the task
dependency network of Figure~\ref{fig:auto-network}.  Shaded agents
and solid arrows are part of the solution, with unshaded agents and
dashed arrows indicating elements of the problem not part of the
solution.  Note that the Ford Auto Assembler wins an input,
but is inactive.  However, recall that inactive producers are
feasible, hence the solution properties are met.  We refer to the
configuration of an inactive producer acquiring an input in an
allocation as a \defn{dead end}.

% walsh:R1_3
Each producer $\pi$ has some \defn{production cost} $\agentCost{\pi}$ for
providing a unit of its output.  The cost might represent the value $\pi$
could obtain from engaging in some other activity (i.e., its opportunity
cost), or some direct cost incurred in producing its output (but not including
input costs).  Since a producer provides at most one unit of one good, the
total production cost to $\pi$, with output $g$, for allocation $E'$, is
$\agentCost{\pi}$ if $\edge{\pi}{g} \in E'$ and 0 otherwise.

% is $\agentAllocCost{\pi}{\allocPrime} = \sum_{\edge{\pi}{g}

We assume that a consumer has preferences over different possible
goods, but wishes to obtain only a single unit of one good.  Thus, a
consumer $c$ obtains \defn{value} $\agentGoodValue{c}{g}$ for
obtaining a single unit of good $g$, and, for allocation $E'$, obtains
value $\agentAllocValue{c}{\allocPrime} \equiv \max_{\edge{g}{c} \in E'}
\agentGoodValue{c}{g}$.  In depicting task dependency networks, we
display costs and values below the corresponding agent boxes.

\begin{definition}[value of an allocation]
\label{def:soln-value}
The \emph{value of allocation} $(V',E')$ is:
\[
\solnValue{\allocPrime} \equiv
\sum_{c \in C} \agentAllocValue{c}{(V',E')}
- \sum_{\pi \in \Pi} \agentAllocCost{\pi}{(V',E')}.
\]
\end{definition}

\begin{definition}[efficient allocations]
The set of
\emph{efficient allocations} contains all feasible
allocations $\allocStar$ such that:
\[
\solnValue{\allocStar} =
\max_{\allocPrime \subseteq \network} (\solnValue{\allocPrime} \; | \;
\allocPrime \mbox{ is feasible}).
\]
\end{definition}

Task dependency networks describe the supply chain formation
problem from a global perspective.  In a decentralized approach to
formation, we would generally not assume that an agent, or any other
entity, has perfect or complete knowledge of the entire
network.  We generally do assume that all agents have perfect knowledge
of their own costs, values, and goods of interest.  When mediators
facilitate the
negotiations for goods (as in protocols described below), each agent
knows of relevant mediators for its goods of interest.  This knowledge
includes all rules enforced by the mediators.  Likewise, mediators
know of the existence of all agents interested in their respective
goods.  Beyond that, a mediator knows only what the agents reveal
through communication during negotiation.  A mediator does not know
the agents' true costs or valuations, nor is it aware of agents'
preferences for goods outside of its direct scope of facilitation.  We
do not address in detail how agents and mediators achieve mutual
awareness (i.e., how connections originate), but assume that it can be
accomplished via some unspecified search, notification, or broadcast protocol.

\section{Resource Contention}
\label{sec:resource-cont-prob}

One natural candidate approach to supply chain formation is the
\textsc{contract net} protocol~\shortcite{Davis83}, the most widely studied
algorithm for forming task performance relations among distributed agents.�
\textsc{Contract net} does indeed apply to our framework, as it employs local
negotiation to achieve a hierarchical task decomposition.� Although definitive
characterization is difficult due to the many variants on \textsc{contract
  net} in the literature~\shortcite{Baker95,Davis83,Dellarocas00a,Sandholm93},
it is fair to say that, generally, ``request for quotes'' proceed top down
from the root task (right-to-left from consumers, in our network terminology),
and contracting proceeds bottom-up (left-to-right towards consumers),
selecting at each level among candidate ``bids'' received.� (Variants of the
protocol are primarily distinguished by the form of bids and selection
criteria employed.)� As a consequence, choices are made greedily, without
reflecting ramifications upstream in the evolving chain.


\begin{figure}[htbp]
�
\centerline{\resizebox{4in}{!}{\includegraphics{Graphics/greedy-bad.eps}}}
�������� \caption{Network \netname{greedy-bad}: A network for which
���������� greedy protocols can produce infeasible allocations.}
�������� \label{fig:greedy-bad}
\end{figure}

This approach can form satisficing supply chains when there are sufficient
resources to support the greedy selection.� However, the basic
\textsc{contract net} protocol does not explicitly address resource scarcity
or contention among multiple agents.� Producers accept bids on inputs before
it can be established whether this might cause infeasibility further
upstream.� Without lookahead or backtracking, \textsc{contract net} might
construct infeasible supply chains when there are limited resources.

For instance, a greedy protocol would not produce a solution for the
network shown in Figure~\ref{fig:greedy-bad}.� Here, if all producers bid
according to a common function monotone in cost, the output bid of
producer \name{a6} would be preferred to that of \name{a5}, because
\name{a6} can acquire its inputs cheaper.� But since \name{a7} must
acquire the one available unit of good \name{4} to feasibly
participate in a solution, \name{a6} cannot be a part of the solution.

The issue of resource contention motivates our adoption of a
market-based approach.� The key idea is that prices can signal
resource value and scarcity up and down the chain, enabling local
decision making while avoiding the pitfalls of greedy one-pass
selection or communication of global structure information.

% To address such problems caused by resource contention, in
% Section~\ref{sec:samp-sb-protocol} we present a decentralized,
% iterative market protocol, \sampsb.� We do not present an in-depth
% comparison between the performance of \sampsb\ and \textsc{contract
% net} because, to our knowledge, there does not exist not a
% sufficiently formalized description of \textsc{contract net}, for 
% clearly defined class of supply chain problems, that would allow for
% precise and detailed comparisons.
%
% With certain assumptions about agent behavior, \sampsb\ always
% constructs feasible allocations.� \sampsb\ can form a solution for
% Network \netname{greedy-bad}, with the costs and values shown in
% Figure~\ref{fig:greedy-bad}.� Although \sampsb\ is not guaranteed to
% form a solution in all cases, we prove positive convergence results for
% special classes of networks, and in Section~\ref{sec:experiments} we
% present empirical results indicating a tendency to form high-value
% solutions.

\section{Price Systems}
\label{sec:price-systems}

% Task dependency networks can be viewed as variants of AND/OR graphs,
% with additional constraints imposed by resource contention.� One could
% thus find solutions to task dependency networks in a centralized
% manner via AND/OR search techniques with extra bookkeeping to account
% for the added constraints.� Alternatively, the problem of finding
% efficient allocations can be cast as a mixed integer-linear
% programming problem and solved with fast commercial software, as we
% describe in Section~\ref{sec:setup}.� However, we focus on
% decentralized approaches, taking as a premise the constraint that
% agents operate autonomously with private information about costs,
% values, and production capabilities.

A \defn{price system}
% provides an economic framework for guiding the allocation decisions of
% agents in a decentralized fashion.� A price system
$p$ assigns to each good $g$, a nonnegative number $\price{g}$ as its
\defn{price}.� Prices are anonymous (i.e., not agent dependent) and linear in
the quantity of goods.� Intuitively, prices indicate the relative value of the
goods, and agents use the prices to guide their local decision making.
% In this section, we identify structures on price systems
% from which desirable properties arise with decentralized, rational
% agent decision making.

We assume agents have \defn{quasilinear} utility functions, defined by
``money'' holdings plus the value (or
minus cost) associated with the allocation of goods.� Agents wish to
maximize their \defn{surplus} with respect to prevailing prices.

\begin{definition}[surplus]
�� The \emph{surplus}, $\surplus{a}{\allocPrime}{p}$, of agent $a$ with
�� allocation $\allocPrime$ at prices $p$, is given
�� by:
\begin{itemize}
\item $\agentAllocValue{a}{\allocPrime} - \sum_{\edge{g}{a} \in E'}
�� \price{g}$, if $a \in C$
\item $\sum_{\edge{a}{g} \in E'} \price{g} - \sum_{\edge{g}{a} \in E'}
�� \price{g} - \agentAllocCost{\pi}{\allocPrime}$, if $a \in \Pi$.
\end{itemize}
\end{definition}


\subsection{Price Equilibrium}
\label{sec:equilibrium}

Generally, an allocation $\allocPrime$ is a \defn{competitive equilibrium} at
prices $p$ if $\allocPrime$ is feasible and assigns to each agent an
allocation that optimizes the agent's surplus at $p$.� For our model, this
means specifically:
% That is, the following constraints on
% prices hold for a feasible allocation $\allocPrime$:
\begin{itemize}
\item % walsh:R1_3
  A producer's optimal choice is to be either active and feasible, or to �
  acquire no goods.� Hence, a producer in the allocation obtains nonnegative �
  surplus by being active, and a producer not in the allocation would obtain �
  nonpositive surplus by being active.
\begin{align*}
� \forall \pi \in \Pi \cap V',\ &
�� \sum_{\edge{\pi}{g} \in E} \price{g} - \sum_{\edge{g}{\pi} \in
�� E}\price{g} - \agentCost{\pi} \geq 0 \\
�� \forall \pi \in \Pi \setminus V',\ &
���� \sum_{\edge{\pi}{g} \in E} \price{g} - \sum_{\edge{g}{\pi} \in
���� E}\price{g} - \agentCost{\pi} \leq 0
\end{align*}
\item % walsh:R1_1
  Because a consumer receives value for obtaining at most one good, a
  consumer's optimal choice is to obtain the good that gives it maximum
  nonnegative surplus, and to obtain no other goods at a positive price.
  Furthermore, a consumer not in the allocation (i.e., not obtaining any
  goods) would obtain nonpositive surplus from any good.
\begin{equation*}
\begin{split}
� \forall c \in� C \cap V',\ & \exists� \edge{g}{c} \in E',\
������� g = \arg\max_{g' \in G} \agentGoodValue{c}{g'} - \price{g'} \\
� & \wedge \agentGoodValue{c}{g} - \price{g} \geq 0 \\
� & \wedge \forall \edge{g'}{E},\ g' \neq g,\ \price{g'} = 0 \\
\forall c \in C \setminus V',\ & \forall g \in G,\ \\
�� & \agentGoodValue{c}{g} - \price{g} \leq 0
\end{split}
\end{equation*}
\end{itemize}

Figure~\ref{fig:equilibrium} shows an example of a competitive equilibrium
for Network \netname{greedy-bad}.� The prices are shown under their respective
goods.

\begin{figure}[htbp]
�
\centerline{\resizebox{4in}{!}{\includegraphics{Graphics/ld-equilibrium.eps}}}
�������� \caption{A competitive equilibrium for Network \netname{greedy-bad}.}
�������� \label{fig:equilibrium}
\end{figure}

A competitive equilibrium allocation is stable in the sense that no
agent would want a different allocation at the equilibrium prices.
Moreover, from equilibrium there is no way to reallocate the resources
(including money transfers) so that some agent has greater surplus,
without degrading some other agent's surplus.� This absence of further
gains from trade is referred to as \defn{Pareto optimality}.� Given
quasilinear utility, price equilibria have been shown to be efficient
under fairly general conditions~\shortcite{Bikhchandani97,Gul99,Ygge98b}.
This also holds for the particular case of task dependency networks,
as stated in Corollary~\ref{cor:equilib-efficient}.

\subsection{Existence of Competitive Equilibrium}
\label{sec:comp-equilib-existence}

Not all task dependency networks have competitive equilibria.� Consider again
Network \netname{greedy-bad} but with $\agentValue{\name{cons}} = 9$, as shown
in Figure~\ref{fig:gb-no-equilibrium}.� The allocation shown is the only
efficient allocation, hence any equilibrium must support it.� Recall that in
equilibrium, active agents must obtain nonnegative surplus, and inactive
producers must not be able to obtain positive surplus.� The price inequalities under
the goods follow from constraints on the
surplus associated with agent activity.� The lower bounds on the
prices of goods \name{1}, \name{2}, and \name{5} ensure that producers
\name{a1}, \name{a2}, and \name{a5}, respectively receiv5e nonnegative
surplus.� The upper bound on \name{3} ensures that \name{a3} could not obtain
positive surplus.� The lower bound on \name{4} ensures that \name{a6} would
receive nonpositive surplus.� Propagating these bounds to \name{6}, we see
that $\price{\text{\name{6}}} \geq 10$ to give \name{a7} positive surplus, but
also that $\price{\text{\name{6}}} \leq 9$ to give \name{cons} nonnegative
surplus.� Since this is impossible, a competitive equilibrium cannot
exist.

\begin{figure}
� \centerline{\resizebox{4in}{!}{\includegraphics{Graphics/greedy-bad-no-equilib.eps}}}
�������� \caption{Network \netname{greedy-bad} with costs and values that do
���������� not support competitive equilibrium.}
�������� \label{fig:gb-no-equilibrium}
\end{figure}

Technically, non-existence of equilibrium is due to complementarity of inputs
for producers with discrete-quantity goods.� In fact, complementarities
are necessary to preclude competitive equilibrium in task dependency networks.
A network has \defn{no input complementarities} when all producers have at
most one input.

\begin{theorem}
\label{th:no-input-comp-eq}
Competitive equilibria exist for any network with no input complementarities.
\end{theorem}
We defer the proof of this and subsequent theorems to
Appendix~\ref{sec:proofs}.

% The proof of this and subsequent theorems are provided in a separate
% appendix titled ``Decentralized Supply Chain Formation: Appendix with Proofs''.



Consider again Figure~\ref{fig:gb-no-equilibrium}.� The multiple undirected
paths between \name{1} and \name{4} give rise to the lower bound on
the price of good~\name{6}.� It turns
out that these undirected cycles are also necessary to preclude competitive
equilibrium.�

A \defn{polytree} is a graph in which there is at most one undirected path
from any vertex to another.� Recall that in task dependency networks,
if a producer uses multiple units of a good, then each unit is represented by
a separate edge.� It follows that an allocation is a polytree iff no more than
one unit of a good is used to produce another given good, or used in multiple
ways to produce a good.

\begin{theorem}
\label{th:polytree-eq}
Competitive equilibria exist for any polytree.
\end{theorem}

% The conditions of this theorem bear some similarity to those of
% Theorem~\ref{th:eq-for-polytree-alloc}.� Note however that
% Theorem~\ref{th:eq-for-polytree-alloc} requires only that the
% \emph{allocation} is a polytree, while Theorem~\ref{th:polytree-eq}
% applies when the \emph{original network} is a polytree, and leads to
% the stronger conclusion of an exact equilibrium.

\subsection{Approximate Price Equilibrium}

We should generally expect that market protocols based on discrete price
adjustments (such as the \sampsb\ protocol we describe in
Section~\ref{sec:samp-sb-protocol}) would overshoot exact equilibria by at
least a small amount.� Therefore, our analysis emphasizes approximate
equilibrium concepts~\shortcite{Demange86,Wellman01}.� We introduce a
particular type of approximation, \defn{\ld-competitive equilibrium}, defined
in terms of parameters that bound the degree to which agents acquire
suboptimal surplus.  Intuitively, $\buyInc$ bounds the suboptimality of a
consumer's surplus, $\sellInc$ bounds the suboptimality of a producer's
surplus attributable to its output, and $\askDiff{\pi}{g}$ bounds the
suboptimality of a producer $\pi$'s surplus attributable to input $g$.  As
described in Section~\ref{sec:samp-sb-protocol}, these parameters also have
special interpretation in our market protocol as applied to task dependency
networks.

% In \sampsb, The $\buyInc$ and $\sellInc$
% parameters correspond to the minimum increment on buy bids and sell bids,
% respectively, and $\askDiff{\pi}{g}$ corresponds to the minimum amount a
% producer would have to bid to buy an input good it is losing.� The
% relationship is characterized formally in
% Section~\ref{sec:sampsb-price-equilib}.

Denote as $\maxSurplus{a}{p}$ the maximum surplus that agent $a$ can
obtain in $(V,E)$, at prices $p$, subject to feasibility.� That
is,
\[
�� \maxSurplus{a}{p} \equiv \max_{\allocPrime \subseteq \network}
�� \surplus{a}{\allocPrime}{p}
\]
such that $a$ is feasible at $\allocPrime$.

\begin{definition}[\ld-competitive equilibrium]
\label{def:ld-compet-eq}
Given the parameters:
\begin{itemize}
\item $\buyInc,\; \sellInc \geq 0$,
\item $\askDiff{\pi}{g}$ for all $\pi \in \Pi$ and all $g \in G$,
% \item $I_\pi = \{\edge{g}{\pi} \in E\}$, $\pi \in \Pi$,
\end{itemize}
an allocation $(V',E')$ is in \emph{\ld-competitive equilibrium} at
prices $p$ iff:
\begin{enumerate}
\item For all $a \in A$, $\surplus{a}{\allocPrime}{p} \geq 0$.
�� \label{cond:eq-pos-surplus}
\item For all $c \in C$, $\surplus{c}{\allocPrime}{p} \geq \maxSurplus{c}{p} -
\consError$. \label{cond:eq-cons}
\item For all $\pi \in \Pi$, $\surplus{\pi}{\allocPrime}{p} \geq
�� \maxSurplus{\pi}{p} - (\prodError{\pi})$, and $\pi$ is feasible at
�� $\allocPrime$. \label{cond:eq-prod}
\item All goods are in material balance. \label{cond:eq-goods}
\end{enumerate}
\end{definition}

Consider Network \netname{greedy-bad} with the same prices shown in
Figure~\ref{fig:equilibrium} except that $\price{\text{\name{5}}} = 8$.� This
does not constitute an exact competitive equilibrium because \name{a6},
though inactive, could make a positive profit.
However, if $\askDiff{\text{\name{a6}}}{\text{\name{2}}} +
\askDiff{\text{\name{a6}}}{\text{\name{3}}} +
\askDiff{\text{\name{a6}}}{\text{\name{4}}} + \sellInc \geq 1$, then since
$\maxSurplus{\text{\name{a6}}}{p} = 1$, \name{a6} obeys Condition~3 and the
allocation is a \ld-competitive equilibrium at the specified prices.

% Figure~\ref{fig:equilibrium} shows a \ld-competitive equilibrium
% for $\lambda_{\text{B-C-D-to-E}} = \delta = 1$.� Goods are indicated
% by circles, consumers and producers with no inputs are represented as
% boxes, and producers are indicated by curved boxes.� A solid arrow
% from a good to an agent indicates that the agent buys the good, and 
% solid arrow from an agent to a good indicates that the agent sells the
% good.� Dashed arrows indicate input/output capabilities not part of
% the allocation.� Shaded agents receive non-null allocations.� Agent
% values and good prices are shown under their respective nodes.� Note
% that for $\pi = \name{\mbox{B-C-D-to-E}}$, $\surplus{\pi}{E'}{p} = 
% \geq \maxSurplus{\pi}{p} - (\prodError{\pi}) = 1 - 4$.� Thus $\pi$
% obeys the producer conditions for \ld-competitive equilibrium.

% A \ld-competitive equilibrium corresponds to the standard notion of 
% competitive equilibrium when $\buyInc = \sellInc = 0$, and \( \askDiff{\pi}{g}
% = 0 \) for all \( \pi \) and \( g \).� Given quasilinear utility, price
% equilibria have been shown to be efficient under fairly general
% conditions~\shortcite{Bikhchandani97,Gul99,Ygge98b}.� This also holds for the
% particular case of task dependency networks.� We demonstrate this by proving
% the more general result that a \ld-competitive equilibrium is suboptimally
% efficient by a fixed bound.


\begin{theorem}
\label{th:ld-equilib-eff-bounds}
�������� If $\allocPrime$ is a \ld-competitive equilibrium for $(V,E)$
�������� at some prices $p$, then $\allocPrime$ is a feasible
�������� allocation with a nonnegative value that differs from the
�������� value of an efficient allocation by at most $\econError$.
\end{theorem}

A \ld-competitive equilibrium corresponds to the standard notion of 
competitive equilibrium when $\buyInc = \sellInc = 0$, and \( \askDiff{\pi}{g}
= 0 \) for all \( \pi \) and \( g \).�
% It immediately follows that a
% competitive equilibrium is efficient.

\begin{corollary}[to Theorem~\ref{th:ld-equilib-eff-bounds}]
\label{cor:equilib-efficient}
A competitive equilibrium allocation is efficient.
\end{corollary}
As noted in Section~\ref{sec:equilibrium}, this is consistent with previously
established results.

% Not all task dependency networks have competitive equilibria.
% Technically, this is due to complementarity of inputs for producers
% with discrete-quantity goods.� However, we can always specify
% $\buyInc$, $\sellInc,$ and $\askDiff{\pi}{g}$ values such that a
% \ld-competitive equilibrium exists, even when a competitive
% equilibrium does not.� We can do this trivially by setting the
% parameters sufficiently high
% such that consumers and producers can obey the \ld-competitive
% equilibrium conditions by exchanging no goods.� Unfortunately, we
% cannot generally specify a \ld-competitive equilibrium for some fixed,
% problem-independent values of $\buyInc$, $\sellInc$, and
% $\askDiff{\pi}{g}$.� In general, the necessary values to obtain 
% \emph{non-solution} \ld-competitive equilibrium are proportional to
% consumer values and producer costs.


% Often, we can specify a \ld-competitive equilibrium to support a
% solution, even when no competitive equilibrium exists.
% Figure~\ref{fig:equilibrium-bounds} shows the constraints on
% $\askDiff{\text{\name{a6}}}{\text{\name{2}}}$,
% $\askDiff{\text{\name{a6}}}{\text{\name{3}}}$,
% $\askDiff{\text{\name{a6}}}{\text{\name{4}}}$, and $\sellInc$ in order
% to support a \emph{solution} in \ld-competitive equilibrium.� The
% underlying network is the \netname{greedy-bad} network, but with 
% different consumer value than shown in
% Figure~\ref{fig:equilibrium}.� With $\agentValue{\name{cons}} = 9$
% (rather than $15$) a perfect competitive equilibrium does not exist,
% hence we need positive values of the \ld\ parameters to obtain a
% \ld-competitive equilibrium.

% The only solution involves all agents except \name{a6}.� The constraints on
% the prices of goods \name{1} and \name{2} ensure that producers \name{a1} and
% \name{a2} sell their outputs.� The constraint on the price of good \name{3}
% ensures that producer \name{a3} does not sell its output.� The constraint on
% the price of good \name{5} ensures that \name{a5} is active.� The constraint
% on the price of good \name{4} ensures that \name{a6} does not trade any goods.
% Finally, the constraint on the price of good \name{6} ensures that \name{a7}
% is active and also that the consumer buys good \name{6}.� The constraint on
% the price of good \name{6} requires
% $\askDiff{\text{\name{a6}}}{\text{\name{2}}} +
% \askDiff{\text{\name{a6}}}{\text{\name{3}}} +
% \askDiff{\text{\name{a6}}}{\text{\name{4}}} + \sellInc \geq 1$ for there to be
% a \ld-competitive equilibrium solution.� Since this solution is the only
% efficient allocation, it is the only candidate allocation for a pure
% competitive equilibrium.� But since the constraints entail some nonzero
% parameter values, there is no pure competitive equilibrium.� Note that to
% sustain the solution in \ld-competitive competitive equilibrium, the
% constraints on the prices for goods~\name{1} and \name{4}, and hence the
% $\sellInc$ and $\lambda$ values, rise linearly with the cost of
% producer~\name{a1}.

% \begin{figure}
�
% \centerline{\resizebox{3in}{!}{\includegraphics{Graphics/no-ld-solution.eps}}}
%��������� \caption{Network \netname{no-\ld-solution}: A network for
%����������� which there does not exist a \ld-competitive equilibrium to
%����������� support a solution.� The inequalities specify constraints on
%����������� prices constrained by the existence of a \ld-competitive
%����������� equilibrium that supports a solution.� }
%��������� \label{fig:no-ld-solution}
% \end{figure}

% There are in fact networks for which no \ld-competitive equilibrium
% exists to support any positive-value solution.
% Figure~\ref{fig:no-ld-solution} shows the constraints on the prices
% necessary for a \ld-competitive equilibrium to support a solution in
% Network \netname{no-\ld-solution}.� Observe that there is one
% positive-value solution in the network.� The constraint on the price
% of good \name{1} is necessary to ensure that producer \name{a2} would
% be active in a solution.� Since producer \name{a3} requires two units
% of good \name{1} to produce its output, we must have
% $\price{\text{\name{2}}} \geq 20$.� But this is higher than the value
% that the consumer \name{cons} has for good~\name{2}, hence there is no
% \ld-competitive equilibrium that supports a solution for this network.

% Observe that the nonexistence of a solution-supporting \ld-competitive
% equilibrium in Network \netname{no-\ld-solution} arises from the fact
% that multiple units of good~\name{1} are required.� A
% \defn{polytree} is a graph in which there is at most one undirected
% path from any vertex to any other vertex.� Note that, in task
% dependency networks, if a producer uses multiple units of a good, then
% each unit is represented by a separate edge.� It follows that an
% allocation is a polytree iff no more than one unit of a good is used
% to produce another given good, or used in multiple ways to produce 
% good.

% \begin{theorem}
% \label{th:eq-for-polytree-alloc}
% If $\allocStar$ is an efficient allocation for $\network$, and
% $\allocStar$ is a polytree, then there exists a \ld-competitive
% equilibrium that supports $\allocStar$.
% \end{theorem}

% \begin{corollary}[to Theorem~\ref{th:eq-for-eff-alloc}]
% \label{cor:ld-eq-always-exists}
% Every task dependency network has a \ld-competitive equilibrium.
% \end{corollary}



% Bikhchandani and
% Mamer~\shortcite{Bikhchandani97} showed that, in exchange economies, 
% competitive equilibrium exists iff the linear program relaxation of
% the mixed-integer-linear program describing the equilibrium conditions
% gives integer allocations (i.e. the linear program gives the same
% result as the mixed-integer-linear program).� It is not immediately
% clear how we might use this result to identify task dependency network
% structures that

\subsection{Valid Solutions}
\label{sec:valid-solutions}

In the following sections we show that \ld-competitive equilibria can
be a useful concept for analyzing decentralized market protocols.
However, such protocols do not always reach \ld-competitive equilibria
for all networks.� Hence we also consider weaker constraints on prices,
consistent with a lesser degree of agent optimization in a solution
allocation.

We say that a solution $(V', E')$ is
\defn{valid} with respect to prices \( p \) if:
\begin{enumerate}
\item Each consumer in the solution pays no more than its value for 
�� a single good.� That is, for all $c \in C \cap V'$, there exists a
�� single $\edge{g}{c} \in E'$ such that
\[ \price{g} \leq \agentGoodValue{c}{g},\]
and $\price{g'} = 0$ for all $g' \neq g$ such that $\edge{g'}{c} \in E'$.
\item None of the active producers are unprofitable.� For all $\pi \in
�� \Pi \cap V'$ where $\edge{\pi}{g_{\pi}} \in E'$ we have
�� $\surplus{\pi}{\allocPrime}{p} \geq 0$.� Note that solution validity
�� does not preclude an \emph{inactive} producer from being
�� unprofitable (i.e., it admits dead ends).
\end{enumerate}
% walsh:R1_5
Note that (1) effectively states that consumers do not obtain negative
utility, which is weaker than the competitive equilibrium conditions in that
it does not require consumers to receive their optimal allocation.  Similarly,
(2) does not require producers to optimize, as in competitive equilibrium, but
only requires nonnegative utility for \emph{active} producers.

\begin{figure}[htbp]
�
\centerline{\resizebox{4in}{!}{\includegraphics{Graphics/valid-solution.eps}}}

\caption{A valid solution for Network \netname{greedy-bad}.}
\label{fig:valid-solution}
\end{figure}

Figure~\ref{fig:valid-solution} shows an example valid solution, with the same
underlying costs and values as in Figure~\ref{fig:equilibrium}.� Because it
allows dead ends, validity does not directly provide useful bounds on the
inefficiency of an allocation.


% By Theorem~\ref{th:eq-for-eff-alloc}, there always exists a
% \ld-competitive equilibrium to support an efficient allocation.� But a
% \ld-competitive equilibria for an efficient allocation is also a valid
% solution, hence valid solutions always exist.


\section{\sampsb\ Protocol}
\label{sec:samp-sb-protocol}

The preceding section introduces some static properties of price
configurations and allocations.  Here we address the problem of how
prices might be obtained.
To compute prices and allocations, we must elicit information bearing
on the relative value of goods, through some
systematic communication process.  Mechanisms that determine
market-based exchanges based on messages from agents are called
\defn{auctions}~\shortcite{McAfee87}.
% Auctions
% serve as mediators for structuring and guiding the negotiation and
% decentralized decision making of the agents.  For a particular domain,
% the engineering problem lies in designing the auction rules to
% encourage desirable outcomes in negotiation.  We would like to attain
% price equilibria when possible, and high-quality allocations in other
% cases.

The agents' \defn{bidding policies} represent their strategies for
interacting with the auctions.  Whereas the auction mechanism may be
designed by a central authority, bidding policies are generally
determined by individual agents.  To understand the implications of
the auction design requires an analysis of the \defn{market protocol}
that arises from the combination the auction mechanism and the agent
bidding policies.

The space of potential auctions is expansive~\shortcite{Wurman01}, and
definitive theoretical results are currently known only for fairly limited
classes of
problems~\shortcite{Bikhchandani97,Demange85,Gul97a,Klemperer99,McAfee87}.
Complementarities with discrete goods, which can cause nonexistence of price
equilibria, also greatly complicate auction design and analysis of
auctions~\shortcite{Milgrom00}.

For our supply-chain domain, we have investigated a particular protocol,
called \defn{\sampsb}\ (Simultaneous Ascending (M+1)st Price with
Simple Bidding).  As demonstrated below,
\sampsb\ can produce good allocations which, in some cases, are
consistent with competitive price equilibrium theory.

\subsection{Auction Mechanism}
\label{sec:auction-mechanism}

The \sampsb\ mechanism comprises a set of auctions, one for each good.
Auctions run simultaneously, asynchronously, and independently, without direct
coordination.  Agents interact with the auctions by submitting bids for goods
they wish to buy or sell.  A bid is of the form: (($q_1$ $p_1$) $\ldots$
($q_n$ $p_n$)).  Each pair ($q_i$ $p_i$) indicates an offer to buy or sell the
good, with $q_i$ indicating the quantity of the offer and $p_i$ indicating the
price.  If $q_i > 0$, it is an offer to buy $q_i$ units of the good for no
more than $p_i$ per unit, and we refer to it as a \defn{buy offer}.  If $q_i <
0$, it is an offer to sell $q_i$ units for no less than $p_i$ per unit, and we
refer to it as a \defn{sell offer}.  Because no agent both buys and sells the
same good in a task dependency network, a bid contains either all positive or
all negative quantity offers.  Bids possess what is sometimes called
``additive-OR'' semantics---the offers are treated exactly as if they came
from separate bids, hence the auction can match any of the individual offers
independently.  Without loss of generality, we henceforth impose the
restriction $|q_i| = 1$ for all offers in all bids, continuing to allow that
agents may submit multiple offers in a bid.

When an auction receives a new bid, it sends each of its bidders a \defn{price
  quote} specifying the price that would result if the auction ended in the
current bid state.  Price quotes are not issued until all initial bids are
received, but are subsequently issued immediately on receipt of new bids.
Because some offers may be tied at the current price, this information alone
is not sufficient for an agent to tell whether it is winning an offer placed
at that price.  To clarify this ambiguity, the price quote also reports to
each bidder the quantity it would buy or sell in the current state.  The same
prices are sent to all bidders, but the reported winning state is specific to
the recipient.  Agents may then choose to revise their bids in response to the
notifications (if an agent does not wish to change its bid, inaction leaves
its previous bid standing in the auction).

% walsh:R1_6
We assume that communication is reliable but
asynchronous.\footnote{Technically, we adopt the model of \emph{asynchronous
    reliable message passing} systems~\shortcite{Fagin95}.}  That is, all
messages sent eventually reach their recipients, although we impose no bound
on the delays.  Agents and auctions use message IDs to ensure that they handle
messages in the appropriate order.  Note that even if all auctions and agents
have deterministic behaviors, an overall run of \sampsb\ may be
nondeterministic due to this asynchrony.

Under asynchrony, it is helpful for the auction to send the ID of
the most recent bid received from the agent with its price quote.  An
agent responds only to a price quote that reflects its most recent bid
sent.  Without this device, an agent can have difficulty establishing
feasibility, as its understanding of its input and output bid states
may be based on nonuniformly delayed reports.

Bidding continues until \defn{quiescence}, a state where all messages
have been received, no agent chooses to revise its bids, and no
auction changes its prices, ask prices, or allocation.  At this point,
the auctions \defn{clear}; each bidder is notified of the final prices
and how many units it transacts in each good.  Note that a quiescent
system is not necessarily in a solution state or (approximate) equilibrium
state.

Although detecting quiescence is straightforward in a centralized
system, in a decentralized, asynchronous system we need to perform the
operation using only local message passing.  In previous
work~\shortcite{Wellman00a}, we described a protocol for detecting
quiescence in general distributed negotiations, based on a well-known
termination-detection algorithm.

Each auction runs according to (M+1)st-price
rules~\shortcite{Satterthwaite89,Satterthwaite93,Wurman98b}.  The (M+1)st
price auction is a variant of the (second-price) Vickrey
auction~\shortcite{Vickrey61}, generalized to allow for the exchange of multiple
units of a good.  Given a set of offers including \( M \) units offered for
sale, the (M+1)st-price auction sets a price equal to the price of the (M+1)st
highest offer over \emph{all} of the offers.  The price can be said to
separate the winners from the losers, in that the winners include all sell
offers strictly below the price and all buy offers strictly above the price.
Some agents that offer at the (M+1)st price also win; in case of ties, offers
submitted earlier have precedence.  Winning buy and sell offers are matched
one-to-one, and pay (or get paid) the (M+1)st price.


When issuing price quotes, the auction reports both the price (i.e., the
current going price, or (M+1)st price), $\price{g}$ and the \defn{ask price},
$\askPrice{g}$ of the good $g$.  The ask price specifies the amount above
which a buyer would have to offer in order to buy the good, given the current
set of offers.  The ask price is determined by the price of the $M$th highest
of all offers in the auction, hence $\askPrice{g} \geq \price{g}$.  For
instance, if we have buy bids 12, 10, and 6 and sell bids 15, 11, and 8,
$\price{g} = 10 $, $\askPrice{g} = 11$, and if the auction is in quiescence,
the buy bids 12 and 10 would match the sell bids 15 and 11 and trade at
$\price{g} = 10$.

Because a producer has complementary inputs, ensuring feasibility is a
challenging problem, requiring careful design.  The auctions run
simultaneously, and each auction requires that the prices of an
agent's successive buy offers increase by no less than some (generally
small) positive number $\buyInc$ and the prices of successive sell
offers increase by no less than $\sellInc$.\footnote{These rules
differ from those of a more typical simultaneous ascending
auction~\shortcite{Demange86,Milgrom00}, which specify that agents must
submit offer prices that are at least an increment above the current
price.}  An auction can enforce the ascending rule by simply
rejecting an agent's offer if the price does not increase by $\buyInc$
or $\sellInc$.  By constraining the direction of price changes, this
design gives producers a more accurate indication of the relative
prices for inputs and outputs than if prices were allowed to fluctuate
in both directions.

The ascending bid restriction ensures ascending auction prices, with one
technicality.  Due to asynchrony and immediate issuance of price quotes, if
the initial bid from an agent arrives after a higher bid, the price quote
could decrease.  This can be handled simply at the auction by issuing no price
quotes until some specified period of time after the auction opens.  After the
first price quote is issued, the auction accepts new bids only from agents
that had previously placed bids.

It is common in auction literature and practice to place an ascending
restriction on buy-offer prices.  It may seem counterintuitive---and is in
fact atypical---to place the same restriction on sell-offer prices.  However,
such an ascending offer price restriction ensures that price quotes rise
monotonically as the auctions progress.  Section~\ref{sec:sampsb-properties}
shows how an ascending--offer-price restriction for both buy and sell offers
serves a key role in establishing the relationships between system quiescence
and solution convergence of the system.

\subsection{Bidding Policies}
\label{sec:bid-policies}


Although designers of negotiation mechanisms do not generally have
control over the agents' behaviors, any conclusions about the outcome
of a mechanism must be based on some assumptions about these
behaviors.  A typical assumption in economics is that agents are
rational in some sense, for example that they play policies that form
a Bayes-Nash equilibrium.  However, as discussed in
Section~\ref{sec:discussion-prices-auctions}, the complexity of supply
chain formation markets is beyond the current state-of-the-art in
analyzing Bayes-Nash equilibria with simultaneous ascending auctions.
Instead, our analysis assumes that the agents follow a simple,
non-strategic bidding policy, described in this section.  Other
variations may be reasonable, or perhaps better in some respects than
the policies we describe.  Rather than explore the range of
possibilities, we chose in this work to investigate a particular set of
policies in depth.  Our chosen policies obey the ascending offer
restriction enforced by the auction, respect the locality of
information in that they require no knowledge of other agents in the
system, and are myopic in that they use only information provided by
the current price quotes, without forecasting future prices.

Recall that a consumer wishes to acquire a single good that maximizes
its surplus at the given prices.  We assume that a consumer initially
offers zero for each good of interest.  So long as it is winning a
good, it does not change its offer.  Whenever it is not winning a
good, it offers $\price{g^*} + \buyInc$ for good $g^* = \arg \max_{g
\in G} (\agentGoodValue{c}{g} - \price{g} - \buyInc)$ if
$\agentGoodValue{c}{g^*}-\price{g^*} -\buyInc \geq 0$, otherwise it
stops bidding.

A producer's objective is much more complex, namely to maximize the difference
between the price it receives for its output and the total price it pays for
its inputs, while remaining feasible.  We assume that a producer initially
offers zero for each of its input goods, and gradually increases these offers
to ensure feasibility.  It raises its offer price for an input good by
$\buyInc$ if and only if the price quotes indicate that it is losing that good
but winning its output.


We assume that producer $\pi$ bids for its output good $g_\pi$ in an effort to
recover its production cost and the \defn{perceived costs} of its inputs.  The
producer places its first output offer only after receiving the first price
quotes for all its inputs, and subsequently updates its output offer whenever
it receives a new price quote on any input.  For simplicity, consider the case
in which $\pi$ has one offer (each at quantity one) for each input.  If $\pi$
is currently winning an input $g$, its perceived cost, $\perCost{\pi}{g}$ of
$g$ is simply $\price{g}$.  When $\pi$ is not currently winning $g$ with a
particular offer, $\perCost{\pi}{g} = \max(\askPrice{g},\; \price{g} +
\buyInc)$.  If $\beta$ is the price of the previous offer made by $\pi$ for
$g_\pi$, then when its perceived costs increase, $\pi$ offers
$\max(\beta+\sellInc,\; \sum_{\edge{g}{\pi} \in E} \perCost{\pi}{g})$ for its
output $g_\pi$.  If $\pi$ has multiple offers for a good $g$, then it assumes
a separate perceived cost with respect to each offer, and bids for its output
accordingly.  Figure~\ref{fig:producer-next-bids} shows how a producer would
bid next as a function of the current prices and its current offers, when
$\buyInc = 1$ and $\sellInc \leq 2$.

% We assume that producer $\pi$ initially offers $\agentCost{\pi}$ to sell its
% output $g_\pi$, and subsequently changes the offer price in an attempt to
% recover the \defn{perceived costs} of its inputs.

\begin{figure}[htbp]
\centerline{\resizebox{3in}{!}{\includegraphics{Graphics/producer-bid.eps}}}
\caption{A producer's next offers, according to \sampsb, when
$\buyInc = 1$ and $\sellInc \leq 2$.  The dashed arrow from
good~\name{B} indicates that the producer is currently
losing \name{B}\@.  The solid arrows indicate that the
producer is currently winning goods \name{A} and~\name{C}.}
\label{fig:producer-next-bids}
\end{figure}

Note that throughout the negotiation, a producer places bids for its
output goods before it has received commitments on its input goods.
Producers counteract potential risk by continually updating their bids
based on price changes and feasibility status.  A producer reduces
exposure to dead ends by incrementing its offer prices on inputs by
minimal amounts and only when necessary.

\subsection{Bidding with General Preferences}
\label{sec:bid-general-pref}

The task dependency network model represents fairly simple production
capabilities and consumer utility.  Here we discuss some natural
potential extensions of the bidding policies to a broader class of
capabilities and preferences.

A producer capable of variable-unit production could bid exactly as if it
were multiple identical producers.  Such a producer would maintain
separate offers
in its bids for each unit, and update the separate offers
independently. Similarly, a consumer with additive value for multiple goods,
or multiple units of a good, could bid for each unit of each good as if it were
a separate consumer.

A producer with alternatives on some input, independent of other inputs,
can switch its bidding to the currently cheapest option.  Subtle issues can
arise for a producer that has alternative input \emph{sets},
particularly when it is tentatively winning parts
of the sets.  One option would be to focus bidding on the set with the lowest
perceived cost, which may include a premium for goods not in the tentatively
winning set.
Alternatively, the producer could assume that it will definitely win its
tentatively won goods and effectively treat them as sunk costs.  Fractional
accounting of sunk costs may also be reasonable.  Similar considerations
arise for extensions presenting complex consumption choices.

\subsection{Properties of \sampsb}
\label{sec:sampsb-properties}

In this section we describe a number of theoretical properties of \sampsb.  In
Section~\ref{sec:quiesc-converge} we describe properties relating to
convergence to quiesence, in Section~\ref{sec:sampsb-price-equilib} we present
properties relating to efficiency and convergence to price equilibrium, and in
Section~\ref{sec:solution-convergence} we present properties relating to
solution convergence.

\subsubsection{Convergence to Quiescence}
\label{sec:quiesc-converge}

The \sampsb\ auctions and bidding policies guarantee that the system will
always reach quiescence.
\begin{theorem}
\label{th:reaches-quiescence}
\sampsb\ reaches quiescence after a finite number of bids have been
placed.
\end{theorem}

However, convergence can take a long time.

\begin{observation}
\label{obs:exponential-bids-quiescence}
In an asynchronous environment, it is possible that a run of the
protocol may require a number of bids that is exponential in the
network size, and not a function of the consumer value.
\end{observation}

\begin{figure}[htbp]
 
\centerline{\resizebox{5in}{!}{\includegraphics{Graphics/exponential.eps}}}
         \caption{Network \netname{exponential}: A network that may require an
           exponential number of bids to reach quiescence.}
         \label{fig:exponential}
\end{figure}

Figure~\ref{fig:exponential} shows Network \netname{exponential},
which illustrates this observation.  The agent named \name{start}
places a one-time bid to sell one unit of good \name{0} for \$2.
Since $\askPrice{\text{\name{0}}} = 2$, and producers \name{1-1} and
\name{1-2} are initially losing their input bids, these agents each
offer a price of 2 for their output goods.  Producer \name{1-3} will
receive the new price quotes for goods \name{1-A} and \name{1-B}
asynchronously, hence may update its bid for good \name{1} twice,
offering a price of 2 the first time and a price of 4 the second time.
Continuing with this process, we see that producer \name{3-3} updates
its bid for good \name{3} up to eight times.  If we extend this
network and maintain labeling consistent with
Figure~\ref{fig:exponential}, then producer \name{n-3} would place
$O(2^n)$ bids for good \name{n}.  Note however, that if bids and price
quotes are propagated synchronously, the exponential growth would not
occur.

In the example above, most of the bids are actually superfluous in that they
do not meaningfully affect the outcome of the protocol.  This appears often
true of situations exhibiting the worst-case behavior described.  To capture
the distinction between relevant and irrelevant bidding, we introduce the
notion of \defn{quasi-quiescence}, a persistent state from which all
subsequent bids effectively do not matter for solution convergence.  \sampsb\ 
convergence to quasi-quiescence requires a number of ``meaningful'' bids that
can be bounded by the size of the network and the value of the maximum
consumer value.

\begin{definition}[quasi-quiescent]
\label{def:quasi-quiescence}
A run of \sampsb\ is in a \emph{quasi-quiescent} state when, for any consumer
or active producer $\tau$, all bids by $\tau$ have been received and $\tau$
would not change its bids in response to any price quotes already received or
transmitted by auctions.
\end{definition}

Clearly, the requirements of quasi-quiescence are subset of the
requirements for quiescence.

\begin{observation}
\label{obs:quiescent-is-quasi}
A quiescent state is a quasi-quiescent state.
\end{observation}

\begin{theorem}
\label{th:quasi-persist}
If a run of \sampsb\ reaches a quasi-quiescent state, then it remains in a
quasi-quiescent state.  Furthermore, neither the allocation nor the prices $p$
subsequently change.
\end{theorem}


% \begin{theorem}
% \label{th:quasi-remains-quasi}
% If a run of \sampsb\ is in a quasi-quiescent state at time $t$, then it is
% quasi-quiescent at all times $t'>t$.
% \end{theorem}


% \begin{theorem}
% \label{th:quasi-active-static}
% If a run of \sampsb\ is in a quasi-quiescent state at time $t$, then
% at any time $t' > t$, a producer that is inactive at $t$ is also
% inactive at $t'$, and a producer that is active at $t$ is also active
% at $t'$.  Furthermore, $\price{g}$ does not change for any good $g$ at time
% $t'$.
% \end{theorem}


% Theorems~\ref{th:quasi-remains-quasi} and~\ref{th:quasi-active-static} mean
% that, once quasi-quiescence is reached, all subsequent bids effectively do not
% matter in terms of equilibrium and solution convergence.

This theorem means that, once quasi-quiescence is reached, all subsequent bids
effectively do not matter in terms of equilibrium and solution convergence.


\begin{corollary}[to Theorem~\ref{th:quasi-persist}]
  The quiescent state of \sampsb\ is a \ld-equilibrium or valid solution iff
  the first quasi-quiescent state reached is a \ld-equilibrium or valid
  solution, respectively.
\end{corollary}


The following theorem establishes a bound on the number of relevant bids
necessary to reach quasi-quiescence.

\begin{theorem}
\label{th:polynomial-quasi-quiescence}
\sampsb\ reaches a quasi-quiescent state after a number of bids
bounded by a polynomial of the size of the network and the value of
the maximum consumer value have been placed by consumers and active
producers.
\end{theorem}
Our previously mentioned quiescence-detection protocol~\shortcite{Wellman00a} can
also detect quasi-quiescence, and thus terminate negotiations when it is
reached.


\subsubsection{Efficiency and Convergence to Price Equilibrium}
\label{sec:sampsb-price-equilib}

We intentionally use $\buyInc$ and $\sellInc$, to parametrize both \sampsb\ 
and our concept of \ld-competitive equilibrium.  With an interpretation of
$\askDiff{\pi}{g}$ in terms of prices and ask prices, we can specify necessary
and sufficient conditions for which the \emph{result} of \sampsb\ corresponds
to a \ld-competitive equilibrium.

\begin{theorem}
\label{th:no-dead-ends-then-equilib}
The prices and allocation determined in quiescence by the \sampsb\ protocol is
a \ld-competitive equilibrium, with $\askDiff{\pi}{g} = \max (\askPrice{g} -
\price{g},\: \buyInc)$, iff no inactive producer buys any positive-price
input.
\end{theorem}

From Theorems~\ref{th:ld-equilib-eff-bounds}
and~\ref{th:no-dead-ends-then-equilib}, we can establish bounds on the
inefficiency of a \ld-competitive equilibrium, parametrized by
$\askDiff{\pi}{g} = \max(\askPrice{g} - \price{g}, \buyInc)$ for each good.
In some cases, the difference between $\askPrice{g}$ and $\price{g}$ may be
quite high.  However, we can actually establish a tighter bound.

% If no inactive producer buys any positive-price input, then by
% Theorems~\ref{th:no-dead-ends-then-equilib}
% and~\ref{th:ld-equilib-eff-bounds}, we can establish bounds on the
% inefficiency of the allocation, parametrized by $\askDiff{\pi}{g} =
% \max(\askPrice{g} - \price{g}, \buyInc)$ for each good.  In some cases, the
% difference between $\askPrice{g}$ and $\price{g}$ may be quite high, resulting
% poor bounds on the inefficiency of the \ld-competitive equilibrium.  However,
% we can establish a bound on inefficiency that is tighter when $\buyInc \leq
% \sellInc$.



% However when $\askPrice{g} - \price{g} > \buyInc$ (in quiescence of \sampsb),
% no agent wins an offer for $g$, so we could raise $\price{g}$ to
% $\askPrice{g}$ and still have a \ld-competitive equilibrium.  We can thus
% construct alternate \ld-competitive equilibrium prices for the same
% allocation, but with $\askDiff{\pi}{g} = \buyInc$ for all $\pi \in \Pi$ and $g
% \in G$.  This gives us a tighter bound on the inefficiency of a
% \ld-competitive equilibrium allocation produced by \sampsb\ (see the proof of
% the following theorem for the details of this argument).

\begin{theorem}
\label{th:sampsb-eq-eff}
If $\allocPrime$ is a \ld-competitive equilibrium computed by
\sampsb, then $\allocPrime$ has a nonnegative value that differs from
the value of an efficient allocation by at most $\sum_{\pi \in \Pi}
(|\{\edge{g}{\pi} \in E\}|\ \buyInc + \sellInc) + |C|\buyInc$.
\end{theorem}
Note that the theorem replaces $\askDiff{\pi}{g}$ from
Theorem~\ref{th:ld-equilib-eff-bounds} with $\buyInc$ in the bound.

A network is a \defn{tree} if it is a polytree with no more than one consumer.

\begin{theorem}
  \label{th:sampsb-tree}
  The quiescent state of  \sampsb\ is a \ld-competitive equilibrium for a
  tree.
\end{theorem}

We are unaware of other general network structures for which \sampsb\ is
guaranteed to converge to a \ld-competitive equilibrium.  However, 
Theorem~\ref{th:no-dead-ends-then-equilib} implies that we can improve
allocations if we modify \sampsb\ to avoid dead ends.  We say that a bidding
policy is \defn{safe} for a producer if the producer cannot obtain a negative
surplus in quiescence.  It is clear that if a protocol is safe for \emph{all}
producers, then it will converge to \ld-competitive equilibrium.

% With the exception of producers with
% no inputs, the \sampsb\ bidding policy is not generally safe for producers,
% and we do not know of any safe producer bidding policy that ensures
% feasibility for any producer in any arbitrary network (other than degenerate
% policies such as not bidding).

In \sampsb\ we have assumed that a producer updates buy and sell offers
simultaneously in response to price quotes.  This policy is not safe, even for
single-input producers, because the producer bids for its input based on the
state of its \emph{standing} offer for its output, rather than the offer it is
about to place.  The producer would get negative surplus if it does not win
its new output offer but gets stuck winning its new input offer.  However, a
slight variant of the bidding policy, which we call \defn{safe \sampsb}, is
safe for any single-input producer.  With this protocol, a producer updates
its input bids only when it would not update, and it currently winning, its
most recent output offer.  Clearly, safe \sampsb\ has the same static
properties as \sampsb, hence Theorem~\ref{th:sampsb-eq-eff} applies to safe
\sampsb.


\begin{theorem}
  \label{th:safe-sampsb}
  The quiescent state of safe \sampsb\ is a \ld-competitive equilibrium for a
  network with no input complementarities.
\end{theorem}

% A \defn{tree} is a polytree with with only one consumer.  The obvious
% multiple-input extension of safe \sampsb, while not generally safe for
% producers with multiple inputs, is safe in a tree network.  


Safe \sampsb\ is not guaranteed to be safe for producers with multiple inputs
in arbitrary networks, nor do we know of any safe producer bidding policy that
ensures safety for producers in any arbitrary network (other than
degenerate policies such as not bidding).

% With the exception of producers with
% no inputs, the \sampsb\ bidding policy is not generally safe for producers,
% and we do not know of any safe producer bidding policy that ensures
% feasibility for any producer in any arbitrary network (other than degenerate
% policies such as not bidding).

Safe \sampsb\ may take longer to reach quiescence than regular \sampsb\@.
With safe \sampsb, a producer must always wait for notification of the results
of pending output offers before increasing input offers.  For a producer to
win an output offer may require propagations of many messages through various
paths in the network before buyers of the output good would increase their buy
offer prices for that good.  The resulting delay would be greater than the
local delay in communicating with the output good auction.

That non-\ld-competitive equilibrium runs of \sampsb\ result in dead ends
suggests a potential source of significant efficiency loss.  For example,
Figure~\ref{fig:valid-solution} shows the result of a run of \sampsb\ on
Network \netname{greedy-bad}.  This valid solution has a dead end at producer
\name{a6}.  Since producer \name{a3} incurs its cost of \$1 to provide good
\name{3} to \name{a6}, but does not contribute to any value in the system,
this dead end is pure waste from a global efficiency perspective.  The
allocation is undesirable directly for producer \name{a6} because it is
committed to pay \$1 for an input it cannot use.  With large networks or
costs, dead ends can result in significant efficiency losses and negative
profits to individual agents.

We propose a \defn{contract decommitment protocol} to remove dead ends after
\sampsb\ reaches quiescence.  According to the decommitment protocol, each
inactive producer can decommit from its contracts for its inputs for which it
would pay a positive price.  The protocol is applied recursively to the
producers that lose their outputs due to decommitment.  When the decommitment
process terminates, agents exchange goods as specified by the remaining
contracts.  We refer to \sampsb\ with decommitment as \defn{\sampsbd}.

In Figure~\ref{fig:valid-solution}, producer \name{a6} would decommit from its
contract with \name{a3}.  Clearly, Theorem~\ref{th:no-dead-ends-then-equilib}
implies that no agent decommits iff \sampsb\ produced a \ld-competitive
equilibrium.  Moreover, if we remove from consideration all producers that
decommit, the remaining agents are in \ld-competitive equilibrium.

Decommitment has the benefit that, whereas some producers can lose
money in the \sampsb\ protocol, no agent receives a negative surplus
from participating in \sampsbd\@.  However, this is achieved by making
the auction allocations non-binding, which is undesirable to the
producers who lose their output sales to decommitments.  It also begs
the question of how to enforce the requirement that inactive producers
be the only agents that decommit.

In addition to dead ends, efficiency can also be lost if \sampsb\
fails to find a solution when a positive value solution exists, or if
\sampsb\ forms a solution with value inferior to an efficient solution
(dead ends are not necessarily mutually exclusive of these two cases).
In Section~\ref{sec:experiments} we describe an experimental analysis
of the efficiency, the source of inefficiency, and
equilibrium attainment of \sampsb\ in a set of networks.


\subsubsection{Solution Convergence}
\label{sec:solution-convergence}


Recall that \sampsb\ always converges to a valid solution (specifically a
\ld-competitive equilibrium) for networks with tree structures, and the safe
variant converges for networks with no input complementarities.  The following
theorem shows that, with sufficiently high consumer value, regular \sampsb\ 
can always converge to a (possibly non-equilibrium) valid solution for
polytrees.

\begin{theorem}
\label{th:polytree-converge}
If $\network$ is a polytree with a solution that assigns good $g$ to
consumer $c$, then given all other costs and values, there exists a
value $\agentGoodValue{c}{g}$ such that \sampsb\ is guaranteed to
converge to a valid solution $\allocPrime$ for $c$.
\end{theorem}
Because dead ends may result, we cannot usefully bound the inefficiency of the
solution reached by \sampsb\ in a polytree.

For general network structures, the prices of all sell offers for all
consumers' goods could rise above their values, in which case the system will
necessarily reach quasi-quiescence in a non-solution state.  If, however,
quasi-quiescence is reached before the price of some consumer's good reaches
its value for the good, we have a valid solution.

\begin{theorem}
\label{th:quiescence-as-valid-soln}
If \sampsb\ reaches quasi-quiescence with $\price{g} <
\agentGoodValue{c}{g}$ for some $\edge{g}{c} \in E$, $c \in C$, then
the system's state represents a valid solution.
\end{theorem}

The next theorem establishes conditions under which a valid solution state
will immediately lead to quasi-quiescence.

\begin{theorem}
\label{th:valid-soln-is-quiescent}
If a run of \sampsb\ in $\network$ is in a valid solution state such
that:
\begin{itemize}
\item each consumer $c$ is either winning an offer or $\price{g} + \buyInc
>   \agentGoodValue{c}{g}$ for all $\edge{g}{c} \in E$,
\item all agents have correct beliefs about which goods they are
   currently winning,
\item all bids from consumers and active producers have been received
   in response to the current price quotes,
\item and no sell offers are lost due to tie breaking,
\end{itemize}
then after the subsequent price quote from each auction, the system
will be in a quasi-quiescent state with a valid solution.
\end{theorem}

Although \sampsb\ is not guaranteed to converge to a solution, the fact that
the problem of finding a solution is NP-Complete~\shortcite{Walsh03} should
lead us to expect that there are problems for which \sampsb\ would converge to
a solution only after an exponential number of meaningful bids.  Since the
number of meaningful bids is bounded by a polynomial of the maximum consumer
value, we should further expect that there exist networks for which \sampsb\ 
can converge to a solution only with a exponential consumer values.  In
practice we find that we can construct problems for which the consumer value
must be exponential in order for \sampsb\ to converge to a
solution~\shortcite{Walsh03}.  However, we have run many simulations for which
the required value is much more reasonable~\shortcite{Walsh03}.

% Cut to save space (seemed like a tangent anyways).
% 
% The proof of NP-completeness relies on a reduction SAT to the problem
% of finding a solution in a task dependency network.  Random 3-SAT
% problems at the phase transition, which are considered the hardest
% problems for SAT algorithms to
% solve~\shortcite{Cheeseman91,Crawford96,Gent94,Mitchell92}, are also very
% difficult for \sampsb\ when encoded as task dependency
% networks~\shortcite{Walsh00}.  However, we have run many simulations for
% which the required value is much more reasonable~\shortcite{Walsh01}.  It 
% remains for
% future work to better characterize the class of task dependency
% networks that require exponential consumer value for convergence.  The
% metrics used by Gent et al.\ to characterize the difficulty of
% NP-complete problems~\shortcite{Gent96b} may provide further insight into
% the performance of \sampsb\ on task dependency networks.

\begin{figure}[htbp]
 
\centerline{\resizebox{5in}{!}{\includegraphics{Graphics/no-converge.eps}}}
         \caption{Network \netname{no-converge}: A network for which
           \sampsb\ cannot converge to a solution for certain values of
           $\buyInc$ and $\sellInc$.}
         \label{fig:no-converge}
\end{figure}

For some networks, costs, and values, \sampsb\ \emph{cannot} converge
to a valid solution with some values of $\buyInc$ and $\sellInc$, no
matter how high the consumer value.  One example (the simplest we
have been able to construct) is Network
\netname{no-converge}, shown in Figure~\ref{fig:no-converge}.  Observe
that a solution must include agent \name{a8}, but cannot include
\name{a7}.  Agent \name{a6} always offers a price of at least
$\price{\text{\name{2}}} + 20$ for good \name{4}, hence \name{a8}
cannot win two units of good \name{4} for less than
$\price{\text{\name{2}}} + 20$ each.  Thus agent \name{a8} will always
offer a price of at least $2\price{\text{\name{2}}} + 40$ for good
\name{5}.  Since agent \name{a7} will never offer a price more than
$2\price{\text{\name{2}}} +
2\askDiff{\text{\name{a7}}}{\text{\name{2}}}$ for good \name{5}, agent
\name{a8} could only win good \name{5} if
$\askDiff{\text{\name{a7}}}{\text{\name{2}}} \geq 20$.  But, for this
to occur, we must have $\buyInc \geq 20$.  A more thorough analysis,
taking into account the dynamics of \sampsb, shows we must have
$\buyInc \geq 40$ and $\sellInc = 0$ to obtain a valid solution in
quiescence, and then only for certain patterns of asynchrony.



% That identifying convergent protocols is nontrivial is supported by
% experience with several variants that fail to reliably terminate in a
% solution state.  For example, the ascending price restriction appears
% pivotal in achieving the desired behavior.

% In various tests, we ran a set of supply chain formation exercises as part of
% classroom assignments.  The first involved 25 human agents playing the role of
% producers, with a variant of our auction mechanism that imposed no restriction
% to ascending offer prices.  The humans failed to reach solutions in any of ten
% problem trials (five different, run twice each), despite the fact that there
% were a multiplicity of solutions, found easily by agents pursuing the simple
% policy presented in Section~\ref{sec:bid-policies}.\footnote{\emph{Note to
%     JAIR reviewers:} we can provide descriptions of this and the subsequently
%   described class exercises in online appendix, with the URL included in the
%   final draft.}

% The second exercise involved over 80 students, each of whom designed a
% software producer to participate in arbitrary task dependency network
% economies.  The economies had simultaneous ascending (M+1)st price
% auctions, but the agents were not constrained to follow the bidding
% policies described in Section~\ref{sec:bid-policies}.  We ran
% subsets of the agents in a number of economies.   A handful of
% trials with homogeneous agent designs (i.e., replications of one
% student's agent) reached solutions.  However, none of the trials with
% heterogeneous agents (i.e., agents designed by different students)
% resulted in solutions.\footnote{
%    The successful completion of this exercise was due largely to the
%    heroic efforts of the class's graduate student instructor, Scott
%    Wallace.}

% We do not draw any serious conclusions from such uncontrolled
% experiments, but report the outcomes as suggestive of the subtlety of
% the underlying problem.

\section{Empirical Performance of \sampsb}
\label{sec:experiments}

Whereas our analytic results provide some insight into
\sampsb\ and its variants, they do not support a comprehensive
characterization of
performance, except for certain special-case network structures.
In order to gain further understanding of the effectiveness of
\sampsb\ and \sampsbd, we performed an empirical study based on
protocol simulations on sample task dependency networks.

\subsection{Setup}
\label{sec:setup}

Our investigation focuses on a
small set of networks exhibiting a variety of structural properties:
\netname{simple} (Figure~\ref{fig:simple-network}),
\netname{unbalanced} (Figure~\ref{fig:unbalanced-network}),
\netname{two-cons} (Figure~\ref{fig:no-equilib-network}),
\netname{bigger} (Figure~\ref{fig:big-many-solns-network}), and
\netname{many-cons} (Figure~\ref{fig:many-cons-network}).  We also also
studied Network \netname{greedy-bad} (Figure~\ref{fig:greedy-bad}).

\begin{figure}[htbp]
\centerline{\resizebox{2in}{!}{\includegraphics{Graphics/simple.eps}}}
\caption{Network \netname{simple}.}
\label{fig:simple-network}
\end{figure}

\begin{figure}[htbp]
\centerline{\resizebox{3.5in}{!}{\includegraphics{Graphics/unbalanced.eps}}}
\caption{Network \netname{unbalanced}.}
\label{fig:unbalanced-network}
\end{figure}

\begin{figure}[htbp]
\centerline{\resizebox{3in}{!}{\includegraphics{Graphics/no-equilib.eps}}}
\caption{Network \netname{two-cons}.}
\label{fig:no-equilib-network}
\end{figure}

\begin{figure}[htbp]
\centerline{\resizebox{4in}{!}{\includegraphics{Graphics/big-many-solns.eps}}}
\caption{Network \netname{bigger}.}
\label{fig:big-many-solns-network}
\end{figure}


\begin{figure}[htbp]
\centerline{\resizebox{3in}{!}{\includegraphics{Graphics/many-cons.eps}}}
\caption{Network \netname{many-cons}.}
\label{fig:many-cons-network}
\end{figure}

We ran experiments on multiple instances of each network.  For each instance
we randomly chose producer costs uniformly from $[0,1]$, but for each consumer
in a network, we calculated a fixed value so that, excluding all other
consumers, there exists a positive-surplus solution for this consumer with 0.9
probability.  We determined consumer values via simulation, assuming the
specified distributions of producer costs.  We discarded all instances whose
efficient solutions had value zero.  We set $\buyInc = \sellInc = .01$.

To test the effect of competitive equilibrium existence on the
performance of the protocols, we generated instances of
\netname{unbalanced}, \netname{two-cons}, and \netname{greedy-bad}
with costs that admit competitive equilibrium and with costs that do
not.  Because \netname{simple} and \netname{many-cons} are polytrees,
we know from Theorem~\ref{th:polytree-eq} that all instances thereof
have competitive equilibria.  We were not able to generate
no-equilibrium instances of \netname{bigger} with the given cost
distributions.

To generate an instance with a desired type of cost structure
(equilibrium or no-equilibrium) we repeatedly chose sets of producer
costs randomly from the uniform distribution until the desired
property was met.  In the experiments, we determined whether
competitive equilibrium existed---given complete information about the
network structure, values, and costs---using the following procedure.
Recall that a competitive equilibrium is always efficient
(Corollary~\ref{cor:equilib-efficient}).  Hence, given an optimal
allocation $\allocStar$, we attempt to solve the system of linear
equations that characterize a competitive equilibrium, as described in
Section~\ref{sec:equilibrium}.  If a solution to the equations exists,
the resulting prices constitute a competitive equilibrium, otherwise
no equilibrium exists.
% \footnote{We could compute \ld-competitive
%   equilibria similarly, with the parameters included in the
%   appropriate equations.}
We used CPLEX, a commercial mixed-integer-linear programming
package, to find the efficient allocation and to solve the
corresponding equilibrium equations.

For each type of cost structure in each network, we tested 100 random
instances, with the exception of \netname{simple}, for which we tested 3220
instances.\footnote{We tested more instances of \netname{simple} as a part of
  a broader study~\shortcite{Walsh00a}.}  For each instance and each protocol,
we measured the \defn{efficiency}---the fraction of the efficient
value---attained by \sampsb\ and \sampsbd\@.  We also measured the percentage
of available surplus (i.e., percentage of the value of an optimal solutions)
obtained by the producers.


\subsection{Results}
\label{sec:results}

We classify the efficiency of a run of the protocols in one of four ways:
Negative, Zero, Suboptimal (but positive), and Optimal efficiency.
Table~\ref{tab:sampsb-eff-classes} shows the distribution of the efficiency
classes in our experiments.  Note that \sampsbd\ cannot produce negative
efficiency, by construction.


\begin{table*}[h!]
\begin{center}
\begin{tabular}{|l | r r r r | r r r|} \hline
    & \multicolumn{4}{c|}{\sampsb} &
      \multicolumn{3}{c|}{\sampsbd} \\
         & \multicolumn{4}{c|}{\% of instances}
         & \multicolumn{3}{c|}{\% of instances} \\
     Network
         & \multicolumn{1}{r}{Neg} & \multicolumn{1}{r}{Zero}
           & \multicolumn{1}{r}{Sub} & \multicolumn{1}{r|}{Opt}
           & \multicolumn{1}{r}{Zero}
           & \multicolumn{1}{r}{Sub} & \multicolumn{1}{r|}{Opt} \\
\hline
    \netname{simple} & 0.0 & 0.3 & 0.0 & 99.7
       & 0.3 & 0.0 & 99.7 \\
     \netname{unbalanced}, case: & & & & & & &  \\
     -- equilibrium exists &  5.0 & 1.0 & 7.0 & 87.0
        & 1.0 & 1.0 & 98.0 \\
     -- no equilibrium exists & 100.0 & 0.0 & 0.0 & 0.0
        & 100.0 & 0.0 & 0.0 \\
    \netname{two-cons}, case:  & & & & & & & \\
     -- equilibrium exists & 11.0 & 0.0 & 6.0 & 83.0
        & 0.0 & 3.0 & 97.0 \\
     -- no equilibrium exists & 18.0 & 0.0 & 78.0 & 4.0
        & 1.0 & 95.0 & 4.0 \\
    \netname{bigger} &  0.0 & 0.0 & 4.0 & 96.0
        & 0.0 & 0.0 & 100.0 \\
\netname{many-cons} & 27.0 & 0.0 & 56.0 & 17.0
        & 0.0 & 2.0 & 98.0 \\
\netname{greedy-bad}, case: & & & & & & &  \\
     -- equilibrium exists & 4.0 & 0.0 & 21.0 & 75.0
                           & 1.0 & 0.0 & 99.0 \\
     -- no equilibrium exists & 100.0 & 0.0 & 0.0 & 0.0
                              & 100.0 & 0.0 & 0.0 \\
\hline
\end{tabular}
\end{center}
\caption{Distribution of efficiency classes from \sampsb\ and
         \sampsbd\@.   Efficiency classes: Negative (Neg), Zero,
         Suboptimal (Sub), and Optimal (Opt).}
\label{tab:sampsb-eff-classes}
\end{table*}


Recall (from Section~\ref{sec:sampsb-price-equilib}) that efficiency loss in
\sampsb\ can be attributable to any of three, not necessarily
exclusive, causes: dead ends, failure to form a solution when a
positive-valued solution exists, and finding a suboptimal solution.
% To identify the prevalence of these causes, we partition the
% efficiency attained by a protocol in an instance of a network into one
% of four qualitative classes: Negative, Zero, Suboptimal (but
% positive), and Optimal.
We can infer the percentage of instances exhibiting dead-end
suboptimality in \sampsb\ by examining the differences between
\sampsbd\ and \sampsb\ totaled over the Negative, Zero, and Suboptimal
columns in Table~\ref{tab:sampsb-eff-classes}.  Decommitment does not
affect the contribution of no-solution and suboptimal-solution
losses, but helps reveal them by eliminating dead-end
suboptimality.  Hence, we can infer the percentage of instances
exhibiting no-solution and suboptimal-solution suboptimality in
\sampsb\ by examining the Zero and Suboptimal columns of \sampsbd,
respectively.


\begin{table*}[htbp]
\begin{center}
\begin{tabular}{|l r r|} \hline
Network                 
  & \multicolumn{1}{c}{\sampsb}
                 & \multicolumn{1}{c|}{\sampsbd} \\
\hline
\netname{simple} & 0.997 & 0.997 \\
\netname{unbalanced} & & \\
   -- equilibrium exists  & 0.867 & 0.990 \\
   -- no equilibrium exists & $-20.080$ & 0.000 \\
\netname{two-cons}, case:  & & \\
    -- equilibrium exists  & 0.733 & 0.986 \\
    -- no equilibrium exists  & 0.268 & 0.686 \\
\netname{bigger} & 1.000 & 1.000 \\
\netname{many-cons}  & 0.120 & 0.996 \\
\netname{greedy-bad}, case:  & & \\
    -- equilibrium exists: & $-5.320$ & 0.990 \\
    -- no equilibrium exists:  & $-18.230$ & 0.000 \\
\hline
\end{tabular}
\end{center}
\caption{Average efficiency in each network for the protocols.}
\label{tab:avg-effs}
\end{table*}

Table~\ref{tab:avg-effs} shows the average efficiency attained by the
protocols, factored by network and equilibrium existence (where
relevant).  We see, from the difference between the \sampsbd\ and
\sampsb\ columns, that dead ends are a significant source of
inefficiency.  Additionally, existence of competitive equilibrium has
a significant effect on the performance of the protocols.  In these
networks, \sampsbd\ produces nearly perfect efficiency when
competitive equilibrium exists (recall that all studied instances of
\netname{simple}, \netname{bigger}, and \netname{many-cons} have
equilibria), but is is much less effective when equilibrium does not
exist, in fact failing to find any solutions in the no-equilibrium
cases of \netname{unbalanced} and \netname{greedy-bad}.


\begin{table}[htbp!]
\begin{center}
\begin{tabular}{|l  l l|} \hline
Network & \multicolumn{1}{c}{\sampsb} &
    \multicolumn{1}{c|}{\sampsbd} \\
\hline  & & \\
\netname{unbalanced} & $6.27\times10^{-30}$
            & $8.23\times10^{-101}$ \\
\netname{two-cons} & $5.15\times 10^{-7}$ &
  $1.43\times 10^{-22}$ \\
\netname{greedy-bad}  & $1.41\times 10^{-1}$ &
  $8.04\times 10^{-101}$ \\
\hline
\end{tabular}
\end{center}
\caption{P-values computed with the Student's t-Test.   The t-Test
  compared the means efficiencies of instances that admit competitive
  equilibrium and those that do  not admit competitive equilibrium.}
\label{tab:eff-t-tests}
\end{table}


To check whether these differences in performance are significant, we
performed Student's t-Tests for each protocol, comparing the mean efficiencies
of instances that admit competitive equilibrium with the means of those
instances that do not admit competitive equilibrium.
Table~\ref{tab:eff-t-tests} shows the results, indicating the p-values that
the means of equilibrium and no-equilibrium instances came from the same
underlying population.  In typical analyses, the null hypothesis that the
means are equal is rejected if the p-value is below $0.05$.  With this
threshold, it seems we can safely reject the hypothesis that the mean
efficiencies of equilibrium and non-equilibrium instances are the same for
Networks \netname{unbalanced} and \netname{greedy-bad}.  Inspection of the
data further supports this conclusion, as \sampsbd\ essentially always
produces zero efficiency, but produces perfect efficiency in many of the
instances that do admit competitive equilibrium.

On the face of it, the high \sampsb/\netname{greedy-bad} p-value suggests that
we cannot safely reject the hypothesis that the mean efficiencies differ
between the equilibrium and no-equilibrium instances of the network.  However,
inspection of the data indicates that this high probability results from one
outlying equilibrium instance with a large negative efficiency.  Indeed, the
fact that \sampsbd\ always produces essentially optimal results in instances
that admit competitive equilibrium, but predominantly produces suboptimal
results in the instances without such equilibria, suggests
that it is unlikely that the equilibrium and no-equilibrium means are the same
for \sampsb\ in Network \netname{greedy-bad}.


\begin{table*}[htbp!]
\begin{center}
\begin{tabular}{|l r |} \hline
   & \multicolumn{1}{c|}{\% \ld-Competitive} \\
Network & \multicolumn{1}{c|}{Equilibrium} \\
\hline
\netname{simple} & 100 \\
\netname{unbalanced} &  \\
   -- equilibrium exists & 88 \\
   -- no equilibrium exists & 0 \\
\netname{two-cons}, case: & \\
    -- equilibrium exists & 83 \\
   -- no equilibrium exists & 2 \\
\netname{bigger} & 96  \\
\netname{many-cons} & 17  \\
\netname{greedy-bad}, case: & \\
   -- equilibrium exists & 75 \\
   -- no equilibrium exists & 0 \\
\hline
\end{tabular}
\end{center}
\caption{Percentage of instances in which \sampsb\ attained
          \ld-competitive equilibrium.}
\label{tab:ld-eq-attain}
\end{table*}


Table~\ref{tab:ld-eq-attain} shows the percentage of instances for which
\sampsb\ attained \ld-competitive equilibrium in each network.  It is
straightforward to determine whether \ld-competitive equilibrium is attained
by observing whether there are any dead ends
(Theorem~\ref{th:no-dead-ends-then-equilib}).  Again, we see a strong
connection with the existence of competitive equilibrium.  One notable
exception is \netname{many-cons} (which always admits a competitive
equilibrium), for which \sampsb\ frequently produced dead ends.  We do see
that \ld-competitive equilibria form in a small percentage of the
no-equilibrium \netname{two-cons} instances, although this is not a prevalent
phenomenon with the $\buyInc$ and $\sellInc$ parameters we chose.

% Because the existence of \ld-competitive
% equilibria that support an efficient allocation may require high
% values of $\buyInc$ and $\sellInc$ (Section~\ref{sec:equilibrium}), it
% is conceivable that \sampsb\ could attain \ld-competitive equilibria
% more frequently with higher values of these parameters.  However,
% convergence to a solution generally requires iteration of \sampsb, and
% high values of the bidding parameters increase the chance that the
% offers will overshoot the consumer values before \sampsb\ can
% successfully find a solution.

\begin{table*}[htbp!]
\begin{center}
\begin{tabular}{|l r r c|} \hline
  & \multicolumn{2}{c}{\ld-Equilibrium}
  & \multicolumn{1}{c|}{\ld-Equilibrium}  \\
  & \multicolumn{2}{c}{Not Found}
  & \multicolumn{1}{c|}{Found}  \\
Network  &  \multicolumn{1}{c}{\sampsb} &
          \multicolumn{1}{c}{\sampsbd}
          &  \multicolumn{1}{c|}{\sampsb / \sampsbd} \\
\hline
\netname{simple} & N/A & N/A & 0.997  \\
\netname{unbalanced} & & &  \\
   -- equilibrium exists & $-0.248$ & 0.989 & 0.998  \\
   -- no equilibrium exists & $-20.08$ & 0.000 & N/A   \\
\netname{two-cons}, case: & & &  \\
    -- equilibrium exists & $-0.570$ & 0.920 & 1.000  \\
    -- no equilibrium exists & 0.130 & 0.707 & 1.000  \\
\netname{bigger} & 0.997 & 1.000 & 1.000  \\
\netname{many-cons} & $-0.060$ & 0.995 & 1.000  \\
\netname{greedy-bad}, case: & & &  \\
    -- equilibrium exists & $-24.28$ & 0.960 & 1.000  \\
    -- no equilibrium exists & $-18.22$ & 0.000 & N/A  \\
\hline
\end{tabular}
\end{center}
\caption{Average efficiency in each network for the protocols,
          factored by \ld-competitive equilibrium attainment.}
\label{tab:avg-effs-by-eq}
\end{table*}

\begin{sloppypar}
Table~\ref{tab:avg-effs-by-eq} shows the average efficiency, factored by
\ld-competitive equilibrium attainment (\sampsb\ and \sampsbd\ produce the
same results when \ld-competitive equilibrium is attained).  We must be
careful in drawing conclusions from these statistics because, for any given
network case, there were relatively few or many \ld-competitive equilibrium
instances (Table~\ref{tab:ld-eq-attain}).  Still, we note certain salient
trends.  The \ld-competitive equilibrium runs produce near perfect efficiency,
with smaller degrees of inefficiency than specified by the bounds in
Theorem~\ref{th:sampsb-eq-eff}.  Because an allocation produced by \sampsb\ is
a \ld-competitive equilibrium iff there are no dead ends, we should expect
that a significant portion of efficiency loss in non-\ld-competitive
equilibrium producing runs of \sampsb\ would be attributable to negative
surplus incurred from dead ends.  The significant differences between the
efficiency of \sampsbd\ and \sampsb\ shown in the non-\ld-competitive
equilibrium column provides evidence for this hypothesis.  Indeed, it appears
that surplus lost to dead ends (as opposed to suboptimal solution attainment)
is the dominant cause of inefficiency when \ld-competitive equilibrium is not
attained.  In all instances, improvement from decommitment is greater than the
difference between the efficiency of \sampsbd\ and optimal efficiency.
\end{sloppypar}

\begin{table*}[h!]
\begin{center}
\begin{tabular}{|l  r c|} \hline
Network
 & \multicolumn{1}{c}{\sampsb} &
          \multicolumn{1}{c|}{\sampsbd} \\
\hline
\netname{simple} & 0.000 & 0.000 \\
\netname{unbalanced}, case:  & & \\
    -- equilibrium exists  & $-0.041$ & 0.082 \\
    -- no equilibrium exists  & $-20.09$ & 0.000 \\
\netname{two-cons}, case:  & & \\
    -- equilibrium exists  & $0.210$ & 0.464 \\
   -- no equilibrium exists  & 0.137 & 0.555 \\
\netname{bigger}  & 0.001 & 0.001 \\
\netname{many-cons}  & $-0.517$ & 0.359 \\
\netname{greedy-bad}, case:  & & \\
    -- equilibrium exists  & $-6.08$ & 0.137 \\
    -- no equilibrium exists  & $-18.11$ & 0.000 \\
\hline
\end{tabular}
\end{center}
\caption{Average fraction of available surplus obtained by producers
in each network for the protocols.}
\label{tab:avg-prod-surp}
\end{table*}



Table~\ref{tab:avg-prod-surp} shows the average fraction of available
surplus obtained by producers, respectively, in each network.  Perhaps
surprisingly, in some networks the producers can gain significant surplus with
the \sampsbd\ protocol, even though they are bidding to obtain zero surplus.
The reason for this is that a producer's output offer indicates the minimum
amount it is willing to accept in exchange for its output.  But rising buy
offers can cause the price to rise above the producer's output offer.  This
could happen in cases when it is necessary to block out certain agents to have
a feasible allocation in quiescence.  Note however, that the decommitment step
is needed for the producers to obtain high average surplus.  Without
decommitment, the average producer surplus can be highly negative, as shown in
the \sampsb\ column.

\section{Related Literature}
\label{sec:related-work}

In this section we discuss literature related to our present work.  In
Section~\ref{sec:discussion-prices-auctions} we discuss related literature on
price-based analysis and auction theory, and in
Section~\ref{sec:related-supp-chain-form} we discuss related literature on
supply chain formation.

\subsection{Price-Based Analysis and Auction Theory}
\label{sec:discussion-prices-auctions}

We have shown some special cases for which competitive equilibria exist in
task dependency networks (polytree and single-input-producer networks), that
\sampsb\ always finds \ld-competitive equilibrium in trees, and that a minor
variant always finds \ld-competitive equilibria in single-input-producer
networks.  A review of the results in price equilibrium and auction theory
reveals that such limited positive results are typical.

It is well-known that given arbitrarily divisible goods and convex
utility, cost, and production functions, competitive equilibrium
prices exist.  If additionally, the gross
substitutes condition (which is a generalization of
no-complementarities) is met, the classic t\^{a}tonnement procedure
finds competitive equilibrium in a distributed manner.\footnote{The
reader may consult a standard microeconomic
textbook~\shortcite{MasColell95} for details on these results.}

When goods are discrete, competitive equilibria exist in exchange
(non-production) economies if the gross substitutes conditions are
met~\shortcite{Bikhchandani97,Gul99,Kelso82}.  Milgrom~\citeyear{Milgrom00} showed
that the existence of a single complementarity can be sufficient to preclude
equilibrium in exchange economies.  Bickhchandani and
Mamer~\citeyear{Bikhchandani97} also show existence under a variety of other
conditions, which do not appear to have natural interpretations in task
dependency networks.  In exchange economies, the gross substitutes condition
also ensures convergence to (approximately) competitive equilibria with
simultaneous ascending auctions~\shortcite{Demange86,Gul97a}.

That distributed price-based auction protocols can leave agents with undesired
goods when their preferences are complementary (e.g., dead ends in a task
dependency network), is a widely recognized problem.  An alternative approach
is to use a \defn{combinatorial auction}, which mediates negotiation at a
single location, performing global matching of combinations of goods based on
indivisible bids.  This general approach has received much attention in the AI
community as of late, motivated in part by techniques for quickly performing
the necessary global
optimization~\shortcite{Andersson:00Integer,Leyton-Brown00a,Sandholm00c}.

Currently, some results on combinatorial equilibria and auctions have been
established for one-sided (i.e., buyer only) bidding.  Bikhchandani and
Ostroy~\citeyear{Bikhchandani02} and Wurman and Wellman~\citeyear{Wurman00a},
using different combinatorial frameworks, provide positive results on
equilibrium existence, and properties thereof.  Wurman and Wellman describe a
combinatorial auction for their framework.  Parkes and
Ungar~\citeyear{Parkes00a} describe a combinatorial auction that is guaranteed
to converge to an efficient allocation if agents follow myopic best-response
strategies.  By adding an ``extend-and-adjust'' phase, these authors are able
to obtain this allocation in \emph{ex post} Nash equilibrium~\shortcite{Parkes02}.
Ausubel and Milgrom~\citeyear{Ausubel02} present a proxy-auction mechanism
that obtains efficient allocations with straightforward bidding in equilibrium
when goods are substitutes.

% walsh:R1_7
In the present work we consider only simple, local, myopic bidding policies.
These policies are non-strategic, in that agents do not reason about their
effect on the negotiations in an attempt to extract greater surplus.  The
assumption of non-strategic behavior is plausible when there are a large
number of agents.  In networks with many agents bidding for individual goods,
many parallel branches, or many agents in sequence, the potential contribution
of any one agent to the value of a solution is relatively small and there is
little to gain by strategic behavior.

Our experiments have shown that, even when producers bid to obtain zero
surplus with the specified policy, they can obtain positive surplus in some
networks.  Nevertheless, in smaller networks, the potential for strategic
improvement is more pronounced, and our non-strategic assumption becomes less
plausible.  A widely studied concept used for analyzing strategic behavior is
Bayes-Nash equilibrium.\footnote{For a foundational reference, Chapter~7 of
  Fudenberg and Tirole's game theory text~\citeyear{Fudenberg98} provides a
  formal treatment of the strategic issues in auction mechanism design and
  analysis.}  Informally, a set of strategies constitutes a Bayes-Nash
equilibrium if no single agent has an incentive to deviate from its strategy,
given that all other agents play their Bayes-Nash equilibrium strategies.
McAfee and McMillan~\citeyear{McAfee87} and Klemperer~\citeyear{Klemperer99}
survey the state of knowledge of strategic analysis of auctions in exchange
economies.  Milgrom~\citeyear{Milgrom00} provides insights on some of the
fundamental challenges to understanding the agent behavior with complementary
preferences.  However, definitive results are known only for quite restrictive
market structures, and do not encompass two-sided markets with
complementarities, never mind the multi-level characteristic of negotiation in
task dependency networks.  The problem of even specifying the information
structure of the extensive form game of simultaneous ascending (M+1)st price
auctions in task dependency networks, prerequisite to computing Bayes-Nash
equilibria, is well beyond the current state of the art in game-theoretic
analysis.

As auction theory currently fails to provide satisfactory guidance for
understanding strategic behavior in even moderately complicated domains, some
have used tournaments as a framework for developing and evaluating candidate
agent strategies.  The Santa Fe Double Auction Tournament~\shortcite{Rust94}
provided some unexpected insights into effective strategies in continuous
double auctions, and the recent ``TAC'' series of trading agent
competitions~\shortcite{TACPaper01,Wellman03gsw} encouraged the development of
sophisticated agent strategies~\shortcite{Greenwald03,Stone02} for a complex
market game.

The Vickrey-Clarke-Groves mechanism~\shortcite{Clarke71,Groves73,Vickrey61}, also
called the Generalized Vickrey Auction (GVA)~\shortcite{MacKie-Mason94}, is a
direct revelation approach, where agents report their valuations on
allocations, and the auction computes a lump-sum payment.  For the GVA, the
solution is the optimal allocation based on the reports, and the payment
function is such that it is a dominant strategy for agents to report their
true utility.  Because of this incentive compatibility and perfect efficiency,
the GVA may seem ideal from an economic perspective (although the computation
can be intractable).  However, the GVA is not budget balanced---when both
buyers and sellers bid, the GVA can pay out more money than it takes in.
Unfortunately this is unavoidable, as it is impossible to simultaneously
ensure efficiency, budget balance, and individual rationality (no agent
achieves negative surplus)~\shortcite{Myerson83}.  Recently, Babaioff et
al.\@~\shortcite{Babaioff01,Babaioff03} described distributed auction mechanisms,
based on McAfee's trade reduction auction~\citeyear{McAfee91}, that obtain
incentive compatibility and budget balance in linear supply chains, at the
expense of perfect efficiency.  Recent work by Parkes, Kalagnanam, and
Eso~\citeyear{Parkes01} explores methods to minimize the deviation from
efficiency while maintaining budget balance in two-sided GVA-like mechanisms.

\subsection{Supply Chain Formation}
\label{sec:related-supp-chain-form}

Supply chain management---the problem of accurately forecasting and planning
production and deliveries to meet demand and minimize inventory---is an active
field of study in operations research.  The problem of management differs from
supply chain formation in that the exchange partners in the supply chain are
pre-established, and it is assumed that information can be gathered from all
agents to effectively optimize global production across the supply chain.  In
contrast, in this work we approached the problem of automating the process of
determining supply chain participants dynamically, under the assumption that
information and decision making is decentralized.  Readers interested in
supply chain management may refer to Kjenstad~\citeyear{Kjenstad98} for an
extensive review.

Relatively less effort has been explicitly devoted to the problem we cast as
supply chain \emph{formation}, despite the rhetorical appeals to decentralized
and dynamic relation-building commonplace in the popular literature.
Nevertheless, as we point out in Section~\ref{sec:resource-cont-prob}, some
venerable AI methods---in particular the widely-known \textsc{contract net}
protocol---can in principle be applied to supply chain formation.  As
discussed in Section~\ref{sec:resource-cont-prob}, the standard
\textsc{contract net} does not have mechanisms to resolve nontrivial resource
contention, precluding a systematic comparison with \sampsb\ on general
network structures.  We can, however, compare the protocols on network
structures for which a resource contention mechanism is not necessary for
\textsc{contract net}.  It is clear that if agents bid their true costs, then
\textsc{contract net} with greedy allocation will converge to optimal
allocations for trees.  The same holds for tree structures relaxed to allow
multiple-unit input bids.  As we have shown, \sampsb\ is guaranteed to
converge to approximately efficient allocations for trees.  However, it can be
shown that it may not converge to good solutions if multiple unit input bids
are allowed.  In the latter case, competitive equilibrium may not exist, and
and we have observed that equilibrium non-existence can substantially hurt
efficiency in \sampsb\ allocations.  In contrast, producers may receive
different prices for the same good with \textsc{contract net}.  This
discriminatory pricing mechanism makes \textsc{contract net} robust in the
presence of complementarities, for this class of network structures.


Sandholm~\citeyear{Sandholm93} examines a specialization of \textsc{contract
  net} for a generalization of Task Oriented Domains
(TODs)~\shortcite{Rosenschein94}.  Agents begin with an initial allocation of tasks
and negotiate task exchanges until there are no mutually beneficial trades.
Sandholm's model allows local constraints on task achievement in that an agent
can perform only certain combinations of tasks.  However, there is no
dependency structure---an agent does not rely on other agents' task
achievement in order to accomplish its own tasks.  Thus, every locally
feasible trade results in a globally feasible allocation, and can be executed
immediately and independently of other trades.  We cannot generally apply an
incremental trading protocol to our task allocation model with subtask
dependencies.  A local exchange may require reallocation throughout the entire
network to maintain production feasibility.

Andersson and Sandholm~\citeyear{Andersson98} find that decommitment protocols
increase the quality of the resulting allocations in variants of TODs.  With
incremental trading, decommitment gives agents the opportunity to engage in
other more cost-effective contracts.  Andersson and Sandholm also consider
decommitment penalties to provide friction in reallocation and to compensate
agents whose contracts are broken.  We expect that such penalties would be an
appropriate extension to the \sampsbd\ protocol.

Veeramani et al.~\shortcite{Veeramani99,Joshi99} consider
issues arising from simultaneous negotiation of multiple subtasking
issues at various levels of a supply chain.  In their asynchronous
model, agents may have the opportunity to finalize a contract while
other negotiations are still pending.  This uncertainty induces a
complex decision problem for agents that do not wish to overextend
their commitments.

Hunsberger and Grosz~\citeyear{Hunsberger00} study the problem of assigning
task performance roles to agents in the SharedPlans collaborative planning
framework.  The model is based on recipes, which describe the precedence
constraints on the execution time across the various sub-tasks that constitute
a complex task.  Contention for shared resources is not modeled explicitly in
the recipe, but individual agents may have additional cost, timing, or other
constraints, potentially arising from their individual resource limitations.
Hunsberger and Grosz use a combinatorial auction to assign tasks to agents,
given the constraints, to produce a high-valued shared plan.  They find that
limiting task assignment to certain combinations in roles can effect a
tradeoff between computational and allocative efficiency.

In other work~\shortcite{Walsh00a,Walsh01a}, we have studied strategic
behavior of agents bidding in a particular one-shot combinatorial auction
within the task dependency network model.  We empirically compared the
performance of \sampsb, \sampsbd, and the combinatorial auction (with
strategic bidding).  The combinatorial auction eliminates the problem of dead
ends by allocating inputs and outputs to producers on an all-or-nothing basis.
This advantage notwithstanding, combinatorial auctions may not always be an
appropriate mechanism.  Since finding any feasible supply chain solution is
NP-hard~\shortcite{Walsh03}, sufficiently large problems will be intractable,
even for advanced optimization procedures.  Even when the computation is
tractable, social factors may limit the authority of any one entity to compute
allocations over the entire supply chain.
 

\section{Extensions and Future Work}
\label{sec:future-work}

The task dependency network model we propose provides a basis for beginning to
understand the automation of supply chain formation.  We have discussed some
ways to extend the bidding policies in our market protocol to accommodate more
general production capabilities and consumer preferences.  With these
extensions we can model capabilities and preferences on multi-attribute goods
(e.g., goods with multiple features such as quality and delivery time, in
addition to price and quantity) by simply representing each configuration as a
distinct good in the network.  However, it is clear that this can explode the
number of goods with just a few attributes.  To effectively handle greater
numbers of attributes would require multiattribute auctions~\shortcite{Bichler01a},
where multiple inseparable features of an exchange are negotiated
simultaneously.

% The task dependency network model we propose has strong representational power
% from a global perspective, and provides a basis for beginning to understand
% the automation of supply chain formation.  However, the transformations
% necessary to model complicated production or demand functions are not
% necessarily strategically equivalent to a more direct model, and may be
% unnatural from an agent's perspective.  An extended model should encompass
% alternate production capabilities, multiple-unit production, more complex
% consumer preferences, and time dependencies.  Although we have suggested how
% some of these might be modeled within the present framework, the necessary
% transformations map multiple agents to a single agent, which would not
% generally give us strategic equivalence.  We could model general
% multiattribute valuations in task dependency networks in a manner similar to
% the method we suggested for modeling discrete-time temporal goods, that is by
% multiplying the goods space.  However, it is clear that this can explode the
% number of goods with just a few attributes.  To effectively handle greater
% numbers of attributes would require multiattribute auctions~\shortcite{Bichler01a},
% where multiple inseparable features of an exchange are negotiated
% simultaneously.

In more realistic scenarios, producers may also have to solve complex
internal scheduling, planning, forecasting, or other complex problems
in order to evaluate their costs and feasible options.  These types of
extensions would increase the fidelity of the model, but would have
implications for agent bidding policies and computation and
convergence speed in market protocols.  Despite the best efforts of
agents to forecast and plan, agents cannot predict with certainty
their operation within a formed supply chain.  Sophisticated agents
would employ probabilistic reasoning techniques in
evaluating their options during negotiation.  When unexpected events
do occur that impair the operation of a formed supply chain, agents
would need protocols for repairing or reforming the supply chain.

We assumed a simple set of non-strategic, myopic bidding policies for the
simultaneous ascending auction.  Because agents must coordinate input and
output bids in a dynamic auction mechanism, understanding strategic bidding
behavior is a challenging and unsolved, albeit important problem for future
work.  It seems likely that significant developments in game-theoretic
methodology would be necessary to analytically solve, or even realistically
specify, the extensive form games of incomplete information corresponding to
asynchronous iterative auctions.  In the meantime, to make progress in
understanding the performance of auctions, we should consider alternate
approaches to developing ``good'' bidding policies.  Tournaments have proven
to be effective ways to both encourage smart people to design smart trading
policies and to evaluate their relative
qualities~\shortcite{Rust94,TACPaper01}.  Axelrod~\citeyear{Axelrod87} used an
evolutionary approach to evaluate populations of strategies, with fixed types,
for the iterated prisoners' dilemma.  A major challenge in applying an
evolutionary approach to the supply chain formation problem is to develop a
sufficiently rich, yet reasonably searchable set of agent bidding policies.

We suggested decommitment as a solution to the problem of dead ends in
\sampsb, and a strategic analysis of the protocol would have to take
this phase into account.  Because producers could not lose money when
decommitment is allowed, we should expect that producers would be more
willing to participate, and would also be more aggressive in
their bidding.  Allowing decommitment begs the question of how to
enforce that producers decommit only when they are in dead ends, and
also does not address the fact that unilateral decisions for
decommitment can potentially break the (possibly desirable) contracts
of many other downstream producers.  To reduce aggressive bidding and
mitigate the potential problems, we could charge penalties to
producers who initiate decommitment~\shortcite{Andersson98}, perhaps
paid to the producers whose output contracts get decommitted.  This
would reduce spurious decommitments while still allowing an out for
producers stuck in costly dead ends.

Finally, we note that the market configuration studied here---separate
auctions for each good---represents just one possible partition of the scope
of negotiations on the supply chain.  At the other extreme, production
activity could be mediated by one combinatorial auction mechanism covering the
entire supply chain~\shortcite{Walsh00a}.  This avoids some coordination
pitfalls of the separate auction approach, but imposes other disadvantages
associated with imposing a mechanism with global scope.  Intermediate
configurations, involving multiple auctions for clusters of highly related
goods, represent a promising alternative for further investigation.

\subsubsection*{Acknowledgments}

This paper includes material previously presented at the Sixteenth
International Joint Conference on Artificial Intelligence
(IJCAI-99)~\shortcite{Walsh99}.  This work was supported in part by
NSF grant IIS-0205435.  

\input{appendix}

\bibliographystyle{theapa}
\bibliography{scjair}

\nocite{Friedman93}
\nocite{Clearwater95}

\end{document}

% local variables:
% compile-command: "make scjair.dvi"
% end:
