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

\usepackage{graphics}
% \usepackage{latexsym}
\usepackage{amsthm}
% \usepackage{amsmath}
% \usepackage{mathptm}

\jairheading{21}{2004}{595-629}{7/03}{5/04}
\ShortHeadings{Concurrent Auctions Across The Supply Chain}
{Babaioff \& Nisan}
\firstpageno{595}

\begin{document}

\title{Concurrent Auctions Across The Supply Chain}

\author{\name Moshe Babaioff \email mosheb@cs.huji.ac.il \\
       \name Noam Nisan \email noam@cs.huji.ac.il \\
       \addr School of Computer Science and Engineering,\\
       The Hebrew University of Jerusalem, Jerusalem 91904, Israel}

% For research notes, remove the comment character in the line below.
% \researchnote{NOTE !!!}

\maketitle
% =========================================================
% \documentclass[12pt]{article} 
% \usepackage{graphics}

%\paperwidth=8.5in
%\paperheight=11in
%\textwidth=6.5in
%\textheight=9in
%% \topmargin=0mm
%\oddsidemargin=0in
%\evensidemargin=0in
 
%% cite auther-year 
%% \let\@internalcite\cite
%\def\fullcite{\def\citeauthoryear##1##2##3{##1, ##3}\@internalcite}
%\def\fullciteA{\def\citeauthoryear##1##2##3{##1}\@internalcite}
%\def\shortcite{\def\citeauthoryear##1##2##3{##2, ##3}\@internalcite}
%\def\shortciteA{\def\citeauthoryear##1##2##3{##2}\@internalcite}
%\def\citeyear{\def\citeauthoryear##1##2##3{##3}\@internalcite}

\newcommand{\ignore}[1]{}

%The following commands define and indent theorem-like environments

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}

\newcommand{\smallspace}{\vspace{.1in}\noindent}


  %Miscellany
\newcommand{\etal}{{\em et al.}}
\newcommand{\half}{\frac{1}{2}}                      %1/2
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor }
\newcommand{\ceiling}[1]{\left\lceil #1 \right\rceil }
\newcommand{\binomial}[2]{\left(
  \begin{array}{@{}c@{}} #1\\[-.5ex]#2 \end{array}
  \right)}                                           %binomial coefficient

\newcommand{\nonneg}{{\cal N}}                       %nonnegative integers
\newcommand{\integers}{{\cal Z}}                     %integers
\newcommand{\zmod}[1]{\integers_{#1}}                %integers modulo #1
\newcommand{\zmodstar}[1]{\zmod{#1}^{\textstyle *}}  %multiplicative subgroup
\newcommand{\bool}{\{0,1\}}                          %{0,1}
\newcommand{\boolstar}{\bool^{\mbox{\small $*$}}}    %{0,1}*


% Comments etc
\newcommand{\cout}[1]{}							% comment out
\newcommand{\cnoam}[1]{{\bf  Noam: #1 \\ }}                 % comment date comment

\newcommand{\notation}{\smallspace {\bf Notation:}}
\newcommand{\notations}{\smallspace {\bf Notations:}}


\newcommand{\stoconly}[1]{{\bf Stoc:} #1}
\newcommand{\gcite}[2]{#2 \cite{#1}}
% \newcommand{\gcite}[2]{\cite{#1}} %stoc -- only ref
%\newcommand{\gcite}[2]{#2}
% TMP !!!!!!!!!!!!!!!!!!!!!!!!! : 
% \input{psfig}
% ----------------------------------------------------------------------
\newcommand{\gconv}[2]{{#1}^{{#2}\to {{#2}+1}}}		% X^{r->r+1}

\newcommand{\supmarket}[0]{M^1}		% M^1
\newcommand{\convmarket}[1]{\gconv{M}{#1}}		% M^{r->r+1}
\newcommand{\demmarket}[0]{M^t}		% M^{t}

\newcommand{\cconv}[2]{S_{#1}^{{#2}\to {{#2}+1}}}		% S_j^{r->r+1}

\def\StretchRtArr#1{{\count255=0 \loop \relbar\joinrel \advance\count255 by1 \ifnum\count255<#1 \repeat \longrightarrow}}
\def\RtOverArrow#1#2{\;{\buildrel #1\over {\StretchRtArr#2}}\;}

\def\StretchLfArr#1{{\count255=0 \loop \relbar\joinrel \advance\count255 by1 \ifnum\count255<#1 \repeat \longleftarrow}}
\def\LfOverArrow#1#2{\;{\buildrel #1\over {\StretchLfArr#2}}\;}
%\def\LfOverArrow#1#2{\;{\buildrel #1\over {\longleftarrow}}\;}

% ----------------------------------------------------------------------


%\title{Concurrent Auctions Across The Supply Chain  \\
%}
%%\footnote{An earlier version of this paper appeared in the 3rd ACM Conference on Electronic Commerce (See~\cite{babaio01concurrent}), full version can be found at~\cite{BabaioffThesis} }
%% NEW (TMP)
% \newcommand{\proof}{{\bf Proof: }}

%\cout{
%\numberofauthors{2}

%\author{
%\alignauthor Moshe Babaioff\titlenote{This research was supported by grants from the Israeli academy of science and the Israeli ministry of science.} \\
%       \affaddr{School of Computer Science and Engineering,}\\
%       \affaddr{The Hebrew University of Jerusalem, Israel}\\
%       \email{mosheb@cs.huji.ac.il}
%\alignauthor Noam Nisan\titlenote{This research was supported by grants from the Israeli academy of science and the Israeli ministry of science.} \\
%       \affaddr{School of Computer Science and Engineering,}\\
%       \affaddr{The Hebrew University of Jerusalem, Israel}\\
%       \email{noam@cs.huji.ac.il}
%}
%} %cout
%\cout{
%\author{Noam Nisan \\
%        Department of Computer Science \\
%       Hebrew University
%\and	Moshe Babaioff \\
%       Department of Computer Science \\
%       Hebrew University}
%\date{15 May, 2002}
%}
%% ENDNEW
%\date{ }

%\begin{document}
  
%\sloppy

%% \maketitle

%\title{ {Concurrent Auctions Across The Supply Chain} \footnote{Partial preliminary version of this paper appeared in the 3rd ACM conference on Electronic Commerce 
%% (See~\cite{babaio01concurrent})
%% , full version can be found at~\cite{BabaioffThesis} 
%} 
%}
%\date{}
%\author{Moshe Babaioff and Noam Nisan
%{\thanks{E-mail:\{mosheb, noam\}@cs.huji.ac.il. Supported by grants from the
%Israeli Ministry of Science, the Israeli Academy of Sciences and the USA-Israel Bi-national Science Foundation.} } \\[2mm]
%\small School of Computer Science and Engineering, \\
%\small The Hebrew University of Jerusalem, Israel} 
%\maketitle{}


%% \thispagestyle{empty}
%%\setlength{\baselinestretch}{4ex}
%\setlength{\baselineskip}{4ex}

\begin{abstract}
With the recent technological feasibility of electronic commerce over the 
Internet,
much attention has been given to the design of electronic markets for various
types of electronically-tradable goods.  Such markets, however, will normally 
need to function in some relationship with markets for other related goods, 
usually those downstream or upstream in the supply chain.  Thus, for example, an electronic market for rubber tires for trucks will likely need to be
strongly influenced by the rubber market as well as by the truck market. \\
In this paper we design protocols for exchange of information between a 
sequence of markets along a single supply chain.  These protocols allow each 
of these markets to function separately, 
while the information exchanged ensures % guarantees 
efficient global behavior across the supply chain.  
Each market that forms a link in
the supply chain operates as a double auction, where the bids on one side of the double auction come from
bidders in the corresponding segment of the industry, and the bids on the other side are synthetically 
generated by the protocol to express the combined information from all other links in the chain.  The
double auctions in each of the markets can be of several types, and we 
study several variants of incentive compatible double auctions, comparing them in terms of their efficiency and of the market revenue.
\end{abstract}

% \pagebreak
% \pagenumbering{arabic}     %no page number on title page
% ---------------------------------------------------------------------------
\section{Introduction}
% MOSHE9.2 \subsection{Motivation}
The recent rush towards electronic commerce over the Internet raises many challenges, both technological
and conceptual.  This paper deals with the conceptual challenge of coordination between electronic
markets.  Let us look only a few years into the technological future of electronic commerce.  It seems very
likely that the following two key challenges will be adequately solved by the industry:
\begin{itemize}
\item
{\bf Supply Chain Integration:}  The enterprise information systems of businesses will be
able to securely and efficiently share information and inter operate with the information systems of their
suppliers, customers, and partners.
\item
{\bf Electronic Markets:} Efficient, sophisticated, robust and liquid electronic markets
will be available for the trade of goods in most segments of the industry. Such markets will interactively
respond to changes in supply and demand, dynamically changing trade quantities and prices.
\end{itemize}

We are interested in the conceptual question of how can markets for related goods share information.
Consider, for example, a fictional market for rubber tires for trucks, and the two related markets
for rubber and for trucks.  One can imagine the following simplified supply chain forming:
rubber manufacturers placing sell bids for rubber in the 
rubber market; tire manufacturers placing buy orders on the rubber market and sell bids on the tire market;
truck manufacturers placing buy bids in the tire market and selling trucks on the truck market; and finally customers
bidding for trucks.  One would expect the combination of these markets together with the information systems 
of the manufacturers
to be able to automatically respond to markets changes in an economically efficient way.  Thus, for example,
a surge in demand for a certain type of trucks, will raise their price in the truck market causing 
manufacturers of this type of truck to automatically decide to increase production, consequently and automatically
raising their electronic bids for tires.  This, in turn, may increase tire prices in the tire market, etc., etc., 
leading, eventually and indirectly,
but still completely automatically, to increased rubber production by rubber manufacturers.  

Let us emphasize: the process just described occurs, slowly, in normal human trade by the 
combined effects of a large
number of self-interested decisions by the many people involved in this supply chain.  What we desire
from the combination of the participating information systems and electronic markets is to automatically (without
human control) and
very rapidly (within the time-frames of electronic commerce),
to reach similar results or even more economically efficient ones than what 
humans usually achieve.  
These results should be achieved
despite the fact that the information systems of manufacturers will still be self-interested -- 
optimizing the company's profit and not the global economic efficiency.

%Since markets of various types, electronic or otherwise, are the usual mechanism for achieving
%economic efficiency from self-interested bids, one would expect that a combination of properly
%designed markets with the self-interested information systems of manufacturers would indeed lead to
%proper economic efficiency.  

Seeing the ``invisible hand'' function in normal human economic activity, one would certainly expect
that electronic markets reach these types of results.
However, a key conceptual design challenge emerges when bidders must be {\em concurrently
active in more than one market}.  Tire manufacturers must concurrently participate as buyers in the rubber
market and as sellers in the tire market.  Clearly, the quantity of rubber they wish to buy at a given price
is determined by the amount of tires they can sell at a given price.
Thus, the price they bid for buying rubber must be intimately related to the price
they bid for selling tires -- any increase in one of them will lead to a corresponding increase in the other.
It is theoretically impossible to define a suggested bid for one without the other.  Thus, if the two markets operate
independently, then the tires manufacturers are not able to reasonably participate in any of them.  If they
operate sequentially, say first rubber is bought and only afterwards tires are sold, then a serious exposure
problem emerges: tire manufacturers must be conservative in their bids for rubber, as they do
not know in advance what price they will get in the tire market.

One approach for handling this inter-dependence of markets is to run the complete supply chain as a single
complex huge market.  Conceptually this is in the spirit of the recently popular ``vertical markets''
and ``vertical portals'' that try to vertically integrate 
information and trade for a complete vertical segment of industry.  The integration of all these markets
into a single complex market results in a complex optimization problem, and some research has been done
to address such problems as pure optimization problems.
%, or also in the context of double-sided combinatorial auctions \cite{XX}. 
 Such a centralized solution has obvious advantages, but 
is also problematic due to necessity of concentrating all information, communications, and decision making 
at a single point.  Such centralization of information is 
 problematic both in the sense of distributed computing systems and in the economic sense.

In this paper we suggest an alternative approach: the supply chain is organized as a sequence of separate markets (which do not act strategically)
that communicate among themselves using a fixed protocol to create a 
distributed mechanism~\cite<for a general overview of distributed algorithmic
mechanism design, we refer the reader to>{feigenbaum-distributed}.  
% A similar approach has been suggested in \cite{WW98,walsh00combinatorial}, 
A similar approach has been suggested by ~\citeA{WW98} and by ~\citeA{walsh00combinatorial}, 
who formulate a general problem that is NP-complete and obtain solutions that are not provably 
efficient, either in the computational sense or in the economic sense. 
A much simpler problem of a linear supply chain
was considered by~\citeA{antoni99tracking}, 
% was considered by Bosch-Domenech and Sunder~\citeyear{antoni99tracking}, 
but no provably efficient protocol was suggested.
We also consider the linear supply chain problem, 
and obtain computationally efficient protocols which achieve provably high 
economic efficiency with budget balance (or full efficiency with budget 
deficit).
%We consider a much simpler problem, and obtain provably efficient protocols.
In our protocols, the intermediate markets along the chain
transform one good into another.  Thus, for example, tire manufacturers place bids for the operation
%In our protocols, the intermediate markets along the chain are semantically for
%transforming one good into another.  Thus, for example, tire manufacturers place bids for the operation
of ``transforming a unit of rubber into a tire''.  The protocol between the different markets assures that
the different markets reach compatible decisions, i.e. that the amount of ``rubber units to tires'' that was
allocated is equal both to the amount of rubber manufactured and to the amount of tires needed.  Furthermore,
these amounts achieve global economic efficiency across the supply chain.  Finally, this result does not
assume that the manufactures information systems have any global knowledge or behavior, beyond their knowledge of
their own cost structure and their self-interested (rational) behavior.

% Moshe9.2 \subsection{Technical Scenario of This Paper}
%\noindent
%{\bf Technical Scenario of this Paper}

%\noindent
This paper focuses on the case of a simple linear supply chain for discrete 
units of goods, where
each manufacturer is able to transform a single unit of one good into a single
 unit of another good, incurring some cost for the transformation.  
Each consumer obtains value from acquiring a single unit of the final good.
%In section~\ref{Extensions} we shortly mention how our results are extended
% to the case of multi-unit bids and to more complicated forms of ``chains'' 
%such as trees (To simplify the exposure of the main ideas, until 
%section~\ref{Extensions} we are presenting our results for the simpler linear 
%supply chain with unit-to-unit conversion).    
We assume that each agent has a quasi-linear utility function, 
and his goal is to maximize his utility.

Each of our markets takes the form of a double auction 
~\cite<see>[for a study of double auction markets]{FriRust91}, 
% (see Friedman and Rust~\citeyear{FriRust91} for a study of double auction markets),
and we consider several variants of double auctions. These variants address four issues:
{\em Incentive Compatibility (IC):} The double auction rules motivate self-interested agents (the manufacturers and consumers)
to reveal their costs / values truthfully  
~\cite<we use the standard notions of dominant strategies IC from Mechanism Design literature;>{MWG95,RO94}.
% (we use the standard notions of dominant strategies IC from Mechanism Design literature,~\citeA{MWG95,RO94}).
{\em Individual Rationality (IR):} Every agent has a strategy which ensures a 
%The auction ensures that an agent that bids truthfully has
 non-negative utility, so agents participate voluntarily (Ex-Post individual rationality).
% {\em Individual Rationality (IR):} All agents have non-negative utility to participate in the auction.
% {\em Economic Efficiency:} The desired outcome should optimize the total utility of all participants;
{\em Economic Efficiency:} The desired outcome should optimize the sum of valuations of all participants.
% specifically, this means that all buyers with valuations above the market clearing price should trade with all sellers whose valuations are below the clearing price.
{\em Budget Balance (BB):} The payment by each buyer does not necessarily equal to the payment received by each seller, but we wish
to ensure that the market mechanism itself does not subsidize the trade.
Thus, the total payment by the buyers
should be at least as the total amount given to sellers.
By~\citeA{Myerson83}
% By Myerson and Satterthwaite~\citeyear{Myerson83}
% By \cite{MWG95} 
impossibility result, these four conditions cannot apply simultaneously. 
%Parkes et al.~\citeyear{parkes01achieving} present 
The paper by~\citeA{parkes01achieving} presents 
mechanisms for combinatorial exchange which are BB and IR but fairly efficient and fairly incentive compatible. We take a different approach and consider
variants that are always IR and IC and trade-off the last two conditions of efficiency and budget balance.
Such a deterministic rule was previously suggested by~\citeA{mcafee92dominant}, but, surprisingly,
 this rule turned out not to be compatible with our supply-chain protocols.
Therefore we suggest two new randomized double auction rules that can be used with our supply-chain protocols, 
and obtain budget balance or surplus but with a slight loss of efficiency.  
We also provide some simulation results comparing the efficiency and budget surplus of the different 
variants of double auctions.

%Specifically, we suggest
%several double auction rules, some of these rules are randomized, that obtain budget balance or surplus but with a slight loss of efficiency.  
%Such a deterministic rule was previously suggested in~\cite{mcafee92dominant} but, surprisingly, this rule turned out 
%to not be compatible with
%our supply-chain protocols. 

The main contribution of this paper is the description
of two alternative protocols that allow a supply chain mechanism formed from
double auctions to operate efficiently.  These protocols are computationally 
efficient in terms of communication and computation time.  
% We prove that when these protocols are applied with our double auction 
% variants, the resulting system exhibits the following three key properties:
We prove that when these protocols are applied with a specific double
auction rule (the Trade Reduction rule), the resulting system exhibits the 
following three key properties:
\begin{enumerate}
\item Ex-post Individual Rationality and Incentive Compatibility (in the sense of dominant strategies).
\item High global economic efficiency (not optimal, but as good as the underlying double auction which guarantees high fraction of the efficient allocation value).
\item Budget Balance.
\end{enumerate}
With our new double auctions, an even higher global economic efficiency
can be achieved in expectation, but with expected (ex-ante) budget balance 
rather than worst case (ex-post).
When these protocols use the VCG~\cite{Vic61,Cla71,Gro73} double auction rule 
which is efficient,
they maintain IR and IC and achieve full economic 
efficiency for the entire supply chain, but with a budget deficit.
%When these protocols use the efficient double auction rule 
%(the VCG rule, for Vickrey, Clarke and Groves~\cite{Vic61,Cla71,Gro73}) 
%we maintain IR and IC and achieve full economic 
%efficiency but have a budget deficit.


Clearly our stylized model is not the most general supply chain model and it 
is far too simple to be a realistic model.
Our purpose in analyzing this model is to present a first step towards a 
mechanism design approach to supply chain problems.
% (a model that fully describe the supply chain of tracks for example, is not compatible with our model).
As far as we know we are the first to design a mechanism that is IC, IR, BB 
and highly efficient for a supply chain model. 

% \pagebreak
%\noindent
%{\bf Paper Organization}

%\noindent
The rest of this paper is structured as follows. 
In Section~\ref{The Lemonade-stand industry} we give a complete self contained
example of the organization of a simple supply chain  
and we demonstrate the type of calculations and information transfer of one of 
our protocols.
In Section~\ref{sec:ic-single} we present the model and conditions for 
incentive compatibility.
In Section~\ref{Incentive compatible double auctions} we summarize the 
properties of several variants of incentive-compatible double auctions and 
present two new randomized double auction rules.  
% Details regarding these double auction rules appear in appendix~\ref{appendix - DA rules}.
In Section~\ref{The protocols} we present two alternative protocols for supply chain coordination between markets, and prove the properties achieved by these protocols, 
% Finally, in Section~\ref{Extensions}, we mention some extensions.
% In Section~\ref{Extensions} we mention some extensions and we conclude in Section~\ref{sec:Future} .
and in Section~\ref{sec:Future} we conclude with directions for future work. 



\section{The Lemonade-Stand Industry}
\label{The Lemonade-stand industry}

Charlie Brown has decided to draw on his vast experience in the lemonade stand
industry and transform the whole industry by bringing it online to the Internet.
Charlie Brown has already struck partnerships with 
strategic players from the three core segments of the industry:

\begin{itemize}
\item {\bf Lemon Pickers:} Alice, Ann, and Abe can pick a lemon
from the neighborhood lemon tree (one lemon maximum per day).
\item {\bf Lemonade Squeezers:} Bob, Barb, and Boris know how to squeeze
a single lemon and make a glass of lemonade from it (one glass maximum per day).
\item {\bf Lemonade Consumers:} Chris, Carol, and Cindy want to buy 
one glass of lemonade each (per day).
\end{itemize}

Charlie Brown has obtained a preliminary version of this paper and has built his
Internet systems accordingly, using
the {\em Symmetric Protocol} suggested here. Charlie Brown has created three
communicating electronic markets: A {\em lemon
market} through which Alice, Anna, and Abe will sell lemons.  A {\em squeezing market} in which
Bob, Barb, and Boris will offer their squeezing services, and a {\em juice market} in which
Chris , Carol, and Cindy can buy lemonade.  

In the first day of operations each of the participants logged into his or her market and 
entered a bid: Alice was asking for \$3 in order to pick a lemon, while Ann wanted \$6, and
Abe (who was living farthest from the tree) wanted \$7.  Bob, Barb, and Boris were asking for, respectively,
\$1, \$3, and \$6 in order to squeeze a lemon, while Chris, Carol, and Cindy, were willing to
pay, respectively, \$12, \$11, and \$7 for their glass of lemonade.  
Figure~\ref{example1a table} presents the three markets, the supply curves 
in the lemon market ($S^L$) and the squeezing market ($S^{L\rightarrow J}$), 
and the demand curve in the juice market ($D^J$).
Knowing that the auction works such that his optimal bidding strategy is to report his true
value or cost, each agent reports truthfully.
Let us follow the operation of 
the system and see how it manages to reach socially efficient allocation and
decide how many lemons should be picked to be squeezed into lemonade.  

\input{table1a.tex}

In the first stage, the markets send information to each other in two phases.
In the first phase, the lemon market aggregates the supply curve for lemons, $S^L$, 
and sends this information to the
squeezing market. The squeezing market aggregates the supply curve for squeezing services, 
$S^{L\rightarrow J}$, adds this vector, point-wise, to $S^L$, and sends the sum to the
juice market.  For the juice market, this sum represents the supply curve for juice, $S^J$, 
aggregated over the complete supply chain. 
As can be seen in Figure~\ref{example1b table}, the cost of the first glass of lemonade is \$4, since the first lemon cost is \$3 and the squeezing operation cost is \$1.
  
\input{table1b.tex}

In the second phase, the juice market sends the demand curve for juice,
$D^J$ to the squeezing market, which subtracts from it, point wise, the supply curve for squeezing services,
sending the difference vector to the lemon market, where this is interpreted as the demand curve for
lemons, $D^L$, aggregated over the complete supply chain.    
As can be seen in Figure~\ref{example1c table}, the demand for the first 
lemon is \$11, since the first glass of lemonade has a demand of \$12 but 
the squeezing operation cost is \$1.

\input{table1c.tex}

The net demand curve for squeezing services,
$D^{L \rightarrow J}$ can now be calculated by the squeezing market to be $D^J - S^L$.
As can be seen in Figure~\ref{example1d table}, the demand for the first 
squeezing operation is \$9 since the first glass of lemonade has a demand of 
\$12 but the first lemon has a cost of \$3. This means that if the lowest 
cost of squeezing operation 
is less than \$9, at least one glass of lemonade can be manufactured.

\input{table1d.tex}

At this point all three markets have both a supply curve and a demand curve, 
and each market can conduct a double auction. 

Being an Internet startup, Charlie Brown has decided to subsidize
the trade in his markets, ignoring the sections
of this paper that aim to eliminate any budget deficit of the markets. 
In each market he thus uses the VCG~\cite{Vic61,Cla71,Gro73} 
double auction rule\footnote{A formal definition of the VCG double auction 
rule appears in Section~\ref{Incentive compatible double auctions}}, 
derived from the Vickrey, Clarke and Groves general auction scheme.
The VCG double auction picks the highest value allocation in each market, so
the winners are the agents in the socially efficient allocation.
The efficient allocation in each market includes the two highest value 
(lowest cost) bidders, since each of the two trades has a positive gain,
and the third trade has a negative gain.
The VCG double auction charges each consumer (demand side) the minimal 
value the agent must bid in order to be in the efficient allocation.
Similarly, each supplier (supply side) receives a payment that equals
the maximal cost it may bid and still be in the efficient allocation.  
The payment takes into account both the competition with other agents of the 
same class and competitiveness of the bid with respect to bids of agents of 
the other classes. With that payment scheme, the best strategy of each agent 
is to bid truthfully. 
%1111111111111111111111111
%He is thus using
%the Generalized Vickrey Auction rule (a.k.a. VCG rule \cite{Vic61,Cla71,Gro73}) in the markets.  Each market now operates separately according to the VCG double auction rule\footnote{A formal definition of the VCG double auction rule appears in Section~\ref{Incentive compatible double auctions}}.
%In the lemon market
%two lemons are sold (by Alice and Ann) for \$7 each (computed as the minimum of \$7, the 
%first non-winning supply bid, and, \$8, the last winning demand bid).  
In the lemon market, two lemons are sold (by Alice and Ann) for 
$ \$7 = min(\$7,\$8) $ each (in order to win, each must bid a cost lower 
than the cost of Abe, the first non-winning lemon supplier, which is \$7.
Each must also bid a cost lower than \$8, otherwise the cost of her lemon 
will be too high to match the lowest demand for a lemon).
In the squeezing
market, two squeezing contracts are awarded (to Bob and Barb) for $ \$5 = min(\$6,\$5)$ each (since if one bids a cost higher than \$5, there will be no demand for his squeezing operation, and the squeezing operation cost of Boris is \$6, which is higher than \$5).
In the juice market, the VCG rule awards two glasses of lemonade (to Chris and Carol)
for the price of $ \$9 = max(\$7,\$9)$ each (since they must bid at least
\$9 to match the supply of juice, and if they do, they also defeat Cindy).  

Charlie Brown is thrilled: the different markets
have all reached the same allocation amount, 2, which, he has verified is indeed the social
optimum:  Society's net gains from trade in his system are $(12+11)-(1+3)-(3+6) = \$10 $, which can't be beaten.
Charlie Browns' investors are somewhat worried by the fact that the system subsidized every glass of lemonade
by \$3 $(=7+5-9)$, but Charlie Brown assures them that changing the 
double-auction rules to one of the other double auction rules suggested in 
this paper can lead to a budget balance or even surplus, while maintaining 
high social gain.  The nine
trading partners have evaluated carefully the operation of this chain of markets and have
assured themselves that they are best served by always bidding their true cost structure.  
% ---------------------------------------------------------------------------
% ---------------- NEW --------------------
\section{IC Mechanisms for Single-Minded Agents}
\label{sec:ic-single}
%We start by presenting a general model that contains our double auction model
% and our supply chain model, and present necessary and sufficient conditions 
%for IC in this model. 
%These results appear in various variants in the literature (Computer Science 
%literature examples are Lehmann et al.~\citeyear{lehmann99truth}, Mu'alem and Nisan~\citeyear{mu'alem02truthful}), and we present the results here for completeness.

Section~\ref{section one-param} presents an abstract model for agents 
that partition the set of outcomes to two, the case they win and the case 
they loss. Each agent has some valuation for the case he wins, and this 
valuation is represented by a single parameter.
The double auction model and the supply chain model we consider are special 
cases of this model. 
The main theorem in this section presents necessary and sufficient conditions 
for incentive compatibility in this abstract model.
~\citeA{mu'alem02truthful} have presented this theorem in the context of 
combinatorial auction with agents that desire one specific bundle that 
is publicly known (the Known Single Minded Model). 
The theorem is derived from a more general result for 
agents with private bundles (the Single Minded Model), proved 
by~\citeA{lehmann99truth}.
Similar result for a different general model with one-parameter agents 
by~\citeA{AT01} appears in the Computer Science literature. 
For completeness, we present the results that are relevant to our 
single-minded agents model.

In section~\ref{sec non-discriminating} we farther restrict the model of 
the single-minded agents to the case of sets of agents that can replace each 
other, and characterize non-discriminating mechanisms for that case.

\subsection{General Model}
\label{section one-param}
In the {\em Single-Minded agents model}, there is a finite set of agents $N$ 
and a set of outcomes $O$.
For each agent $i\in N$, $O$ is partitioned to two disjoint sets 
$O_i^W$ and $O_i^L$, 
the outcomes in which he Wins and the outcomes in which he Loses, respectively
(this partition is public knowledge). 
For any $i$ there is an ordered set of {\em values space} 
$V_i$ for the case he wins. 
Agent $i$ has a private {\em value} $v_i\in V_i$ for any $o\in O_i^W$ 
(he wins) and a value of $0$ for $o\in O_i^L$ (he loses). 
The private values are the only private information, 
all other information is publicly known to all participants and to the 
mechanism (and it is known that the rest of the information is public).
For technical reasons we assume that for any $v_i^1, v_i^2\in V_i$, 
such that $v_i^1> v_i^2$, there exist $v_i^3\in V_i$ such that  
$v_i^1> v_i^3 >v_i^2$ 
(For example $V_i$ can be the set of Real numbers or Rational numbers).
When agent $i$ wins and pays $p_i$ he has a quasi-linear {\em utility} 
$u_i = v_i - p_i$, and in normalized mechanisms he pays $0$ and has $0$ 
utility if he loses.
We assume that agents are self-interested and try to maximize their utility. 
Under this model, an outcome $o\in O$ has a one-to-one mapping to a set of 
winners and is called an {\em allocation} $A$, $A = \{i\in N | o\in O_i^W\}$.
We say that the allocation $A$ is {\em efficient} if 
$\sum_{i\in A} v_i$ is maximized.
The {\em efficiency} of the allocation $\hat{A}$ is 
${\sum_{i\in \hat{A}} v_i} \over  {\sum_{i\in A} v_i}$, where $A$ is an efficient allocation.
Let $V$ be the set of possible values of the agents, 
$V = \prod_{i\in N} V_i $. 
We work with mechanisms in which agents are required to report their values, 
and the mechanism decides the allocation and the payments to the agents in a
deterministic way.
The reported value $b_i\in V_i$ of agent $i$ is called the {\em bid} of the 
agent and might be different from his private value $v_i$. Let $b\in V$ be 
the bids of all agents. 
An {\em allocation rule $R$} decides the allocation according to the reported
values $b\in V$, $R$ is a function $R:V \rightarrow O$. 
A {\em payment rule $P$} decides the payment $p_i$ of agent $i$, 
$P$ is a function $P:V \rightarrow R^N$. 
A {\em mechanism $M$} defines an allocation and a payment rule,  $M=(R,P)$.
Mechanism $M$ is {\em Budget Balanced (BB)} if $\sum_{i} p_i \ge 0 $ for any 
bids $b\in V$. $M$ is {\em Incentive-Compatible (IC) in dominant strategies} 
if for any agent $i$, bidding $v_i$ maximizes $i$'s utility over all possible 
bids of the other agents. 
$M$ is {\em normalized} if losing agents have a payment (and utility) 
of $0$. $M$ is (ex-post) {\em Individually Rational (IR)} if for any agent $i$
and value $v_i$, there is a bid $b_i$ such that when he bids $b_i$, 
$u_i\ge 0$ for all possible bids of the other agents. 
Note that any normalized and incentive-compatible mechanism is 
individually rational (since truthful bidding ensures a non negative utility).


Below we present necessary and sufficient conditions for a
mechanism to be incentive compatible in dominant strategies under the 
 single-minded agents model.
These conditions will later be used to prove properties of our double auctions
and supply chain mechanisms created by our protocols.

For bids $b\in V$ we denote $b=(b_i, b_{-i})$ where $b_{-i}$ is the bids of all
agents but $i$.
\begin{definition}
% Assume that agent $i$ is in the allocation decided by allocation rule $R$ 
% for the bids $b$ when he bids $b_i$.
Allocation rule $R$ is {\bf Bid Monotonic} if for any bids $b\in V$, any agent $i$ and any two possible bids of $i$, $\hat{b_i}>b_i$, 
if $i$ is in the allocation $R(b_i, b_{-i})$ then he is also in the allocation
 $R(\hat{b_i}, b_{-i})$.
\end{definition}
A bid monotonic allocation rule ensures that no winning agent becomes a 
loser by improving his bid.
The following observation is a direct result from the above definition. 
\begin{observation} 
\label{bid monotonic  - critical values}
Let $R$ be a bid monotonic allocation rule, 
let $b\in V$ be a set of bids of the agents and let $i$ be any agent with a 
bid $b_i$.

If there exists a bid $\hat{b_i}$ for $i$ such that $i$ is in the allocation
$R(\hat{b_i}, b_{-i})$, then
there exists a critical value $C_i$ such that 
$i$ wins if he bids $b_i>C_i$ and $i$ loses if he bids $b_i<C_i$ ($C_i$ is 
independent of the bid $b_i$)\footnote{$C_i=-\infty$ if $i$ always wins}.
\end{observation}

Note that if the bid is equal to the critical value, the observation
 does not say if the agent wins or not.

\begin{lemma}
\label{Incentive Compatible is bid monotonic}
Let $M$ be a normalized and IC mechanism with allocation rule $R$. 
Then $R$ is Bid Monotonic.
\end{lemma}

\begin{proof}
Assume in contradiction that the auction is normalized and IC (thus also IR)
but the allocation is not bid monotonic. 
Then there exists an agent $i$ and two values $b_H>b_L$, 
such that $i$ wins the auction and pays $P_L$ if he bids $b_L$, 
and loses the auction and pays zero if he bids $b_H$.
The mechanism is IR therefore $b_L-P_L\ge 0$. 
If $i$'s true value is $b_H$ he can gain by misreporting his private value: 
if he reports his true value he loses the auction and 
has utility zero, but if he bids $b_L$ he wins the auction and pays $P_L$. 
In this case his utility is $b_H-P_L>b_L-P_L\ge 0$ in contradiction to the 
assumption that the auction is IC.
\end{proof}


\begin{theorem}
\label{critical values - Incentive Compatible}
A normalized mechanism $M$ with allocation rule $R$ is IC 
if and only if $R$ is Bid Monotonic and each trading agent $i$ 
pays his critical value $C_i$ ($p_i=C_i$).
\end{theorem}
\begin{proof}
\emph{Case if:}	
  Assume that $M$ is normalized, $R$ is bid monotonic and agent $i$ with 
  value $v_i$ pays $C_i$ if he wins. We first show that the auction is IR,
  we show that $i$ receives non-negative utility from bidding truthfully.  
  If $i$ loses, he pays zero and has zero utility.  If $i$ wins
  the auction by bidding truthfully, then by 
  Observation~\ref{bid monotonic  - critical values},
  $v_i \ge C_i = p_i$, hence his utility is $v_i-p_i = v_i-C_i \ge 0$. 

  To prove IC we prove that $i$ cannot improve his utility by misreporting
  his value. 
  Consider the case in which agent $i$ wins the auction by bidding his true
  value $v_i$.  
  If $i$ bids untruthfully and loses, then he gets zero utility, which
  by IR cannot be better than his utility with a truthful
  bid.  If $i$ bids untruthfully and wins the auction, then 
  since he still pays his critical value $C_i$ his utility remains the same.
  
  Now consider the case in which $i$ loses the auction by bidding truthfully.
  His utility is zero and $v_i\leq C_i$ by 
  Observation~\ref{bid monotonic  - critical values}. 
  If $i$ bids untruthfully and loses, his utility
  remains zero.  If $i$ bids untruthfully and wins, his utility is
  $v_i - C_i \leq 0$.
  In both cases, we have shown that an agent cannot improve his utility by
  bidding untruthfully, thus proving that $M$ is IC.

\emph{Case only if:}
Assume that the auction is normalized and IC (thus also IR). 
By Lemma~\ref{Incentive Compatible is bid monotonic} its allocation rule is
 bid monotonic, so we need to prove that each agent $i$ 
with value $v_i$ must pay his critical value $C_i$. 
Assume that $p_i \neq C_i$ for some agent $i$.
If $p_i>C_i$, then if $p_i>v_i>C_i$ and $i$ bids truthfully, then 
by Observation~\ref{bid monotonic  - critical values} $i$ wins but his utility
is $v_i-p_i<0$ which contradicts individual rationality.
If $p_i<C_i$, then if $p_i<v_i<C_i$ by 
Observation~\ref{bid monotonic  - critical values} $i$ loses and has zero 
utility if he bids truthfully. 
If $i$ misreports his value by bidding $b_i>C_i$, he would win the auction and 
has utility $v_i - p_i >0 $ which contradicts incentive compatibility.
\end{proof}

So for normalized and IC mechanisms, the allocation rule which is bid 
monotonic uniquely defines the critical values for all the agents and thus 
the payments.
\begin{observation}
\label{obs:single-payment}
Let $M1$ and $M2$ be two normalized and IC mechanisms with the same 
allocation rule. 
Then $M1$ and $M2$ must have the same payment rule, which means that 
$M1$ and $M2$ are the same mechanisms.
\end{observation}

% For the supply chain the possible outcomes are the set of feasible allocations.
% Finally we note that a double auction is also a special case of this model, 
% therefore all the above results hold for double auctions as well.

%We conclude that for every IR and IC mechanism, 
% its bid monotonic allocation rule uniquely defines its payment rule.

% }

%\subsection{Agent Types Model}
%We now present a restriction of the general model for single-minded agents to 
%the case where agents are dividable to disjoin groups of ``equivalent''
% agents. For example all sellers of a single item of some homogeneous good
%are of the same agent type (sellers). 

\subsection{Non-Discriminating Mechanisms}
\label{sec non-discriminating}
We are interested in the subclass of mechanisms for single-minded agents 
which do not discriminate between agents that have the same ``roll'' in the 
outcome.  These are agents that can always
% belong to the same equivalence class and can 
replace each other.

% Sometimes we will be interested in mechanisms in which all agents that are ``equivalent'' have the same payments. We start by defining agents equivalency. 
% Both our double auction model and our supply chain model have this 
% property.
\begin{definition}
Agent $i$ has the same {\em class} as agent $j$,
 if for every allocation 
$A$ such that $i\in A$ and $j\notin A$, the allocation 
 $A' = A \setminus \{i\} \cup \{j\}$ is also in $O$, 
and for every allocation 
$A$ such that $i\notin A$ and $j\in A$, the allocation 
 $A' = A \setminus \{j\} \cup \{i\}$ is also in $O$.
\end{definition}
Note that the class of an agent is an equivalence class.
% Clearly by the definition of a class of an agent, we can partition the agents to equivalence classes. 

\begin{definition}
Let $M$ be a mechanism, $T$ be any class of agents and $i,j$ be two agents of 
class $T$.
$M$ is {\em non-discriminating by identity} if 
for any bids $b\in V$, if $i$ wins when he bids $b_i$ and $b_j > b_i$ then 
$j$ also wins.

$M$ has {\em non-discriminating pricing} if for any bids $b\in V$ and 
every class $T$ there is a value $p_T$, such that if agent $i$ of class $T$ 
has a bid $b_i$ and $b_i>p_T$ then $i$ wins and pays $p_T$.

$M$ is {\em non-discriminating (ND)} if it is non-discriminating by identity 
and has non-discriminating pricing.
\end{definition}
Non-discriminating mechanisms are also called Envy-Free mechanisms by~\citeA{envyFree03}, since no loser envies any winner for the fact 
that he won the auction 
or for the price he paid.
In this paper we only consider mechanisms that are non-discriminating by 
identity, which means that agents of the same class are picked by their bid
order, from high to low. Also note that if $M$ is IR and has 
non-discriminating pricing then any agent of class $T$ that bids below $p_T$ 
must lose the auction (otherwise he has a negative utility contradicting IR).

The following observation is a direct result of
 Theorem~\ref{critical values - Incentive Compatible}.
\begin{observation}
\label{obs:same-payment}
Let normalized mechanism $M$ be IC and ND. 
Let $p_T$ be the payment of winners of class $T$. 
Then the critical value for all winning agents of class $T$ is $p_T$.
\end{observation}

% Any IC mechanisms that maximizes the 
% efficiency under any constraints, must be non-discriminating by identity.

% For such mechanisms, note that an allocation rule which should maximize the 
% sum of values over all allocations with some quantity of agents of each type,
% should always pick an allocation with this quantity of the highest value 
% agents of each type.
 
For normalized, IC and ND mechanisms, we prove that the payment of 
winners of the same class are independent of their bids.
\begin{lemma}
\label{lem:ND-price-fixed}
Let normalized $M$ be an IC and ND mechanism. For every agent class
$T$, if agent $j$ of class $T$ wins and pays $p_T$ when he bids $b_j>p_T$ 
and a winning agent $i$ of class $T$ bids $b_i\ge p_T$, 
then $j$ also wins and pays $p_T$ if $i$ bids $\hat{b}_i>b_i$.
\end{lemma}
\begin{proof}
Since $M$ is normalized and IC, then by 
Theorem~\ref{critical values - Incentive Compatible} 
it is bid monotonic and by Observation~\ref{obs:same-payment} 
$p_T$ is the critical value for $i$ and $j$.
By Observation~\ref{bid monotonic  - critical values} $p_T$ is independent of
the bid $b_i$, so $i$ must pay $p_T$ if he bids $\hat{b}_i>b_i$.
Since $M$ is non-discriminating, $j$ must also win (since $b_j>p_T$) and pay $p_T$.
\end{proof}
% ------------------------------------

\section{Incentive Compatible Double Auctions}
\label{Incentive compatible double auctions}

Each of the markets along our supply chain performs a double auction 
% (for a study of double auctions see Friedman and Rust~\citeyear{FriRust91}). 
~\cite<for a study of double auctions see>{FriRust91}. 
Our protocols for supply chains can work with a wide variety of double 
auction rules, and in this section we present several double auction rules
that were suggested in the literature, and two new randomized double auction 
rules that we later use to create supply chain mechanisms.  
A double auction rule decides the trading agents and the payments to the agents.

% NEW PART: Model
We first give a description of the Double Auction (DA) model.
It is a single-minded agents model with the following 
specifications of possible outcomes, value spaces and classes of agents.
%additional restrictions. 
There is some homogeneous good $g$ that is traded in discrete 
quantities, and agents that are of one of two classes of agents. An agent is 
either a {\em seller} or a {\em buyer} of one unit of a good $g$.
Seller $i$ has a single unit of $g$ and has some non-negative cost $s_i$ 
($v_i = -s_i$) if he sells his unit.
Buyer $i$ has a non-negative value $b_i$ ($v_i = b_i$) if he receives one 
unit of good $g$. 
The set of possible allocations are the set of {\em materially balanced} 
allocations, which are allocations with the same number of sellers and buyers.

%We first give a description of the Double Auction (DA) model.
%Let $A$ be the {\em allocation} (outcome) of the auction, 
%which is the set of trading agents (winners).
%Each agent $i$ has a {\em valuation function} $V_i$ over the 
%outcomes of the auction.
%We assume that the agents have no externalities, meaning that each agent 
%care only if he trades or not. 
%Agent $i$'s assign a real {\em value} $v_i$ for allocation $A$ if $i\in A$, 
%and $0$ if $i\notin A$.
%Seller $i$ has a non-negative cost $s_i$ ($v_i = -s_i$) if he sells his unit 
%of the good.
%Buyer $i$ has a non-negative value $b_i$ ($v_i = b_i$) if he receives one 
%unit of the good. 
%If the allocation is $A$ and agent $i$ pays $p_i$, his {\em utility} is 
%$u_i(A) = V_i(A) - p_i$, which is $0$ if he loses and pays $0$, and 
%$v_i-p_i$ if he wins (note that sellers pay non-positive payment, 
%which means that they receive money). 
%%Agents that do not trade and pay zero, have zero utility. 
%We assume that agents are self-interested and try to maximize their utility. 
%We say that the allocation $A$ is {\em efficient} if 
%$\sum_{i} V_i(A) = \sum_{i\in A} v_i$ is maximized.
%We say that the auction is {\em budget balanced} if $\sum_{i} p_i \ge 0 $.


A DA begins by agents reporting their values for one unit of the good.
Each seller $i$ reports a cost $S_i$ which might be different from his real cost $s_i$. 
Each buyer $i$ reports a value $B_i$ which might be different from his real value $b_i$. 
All DA rules are non-discriminating by identity, so they first construct 
the {\em supply and demand curves} by sorting the supply bids s.t. 
$S_1 \le S_2 \le \ldots$ and the demand bids 
s.t. $B_1 \ge B_2 \ge  \ldots$. If agents report truthfully then in order to 
maximize efficiency, once the trade quantity $q$ is set, the trading agents 
must be the first $q$ sellers and the first $q$ buyers. 
{\em The optimal trade quantity} $l$ is defined to be maximal such that 
$B_l\ge S_l$. Trading $l$ units maximizes the efficiency if the agents' bids 
are the agents' true values.
In all double auctions we consider non-trading agents pay zero.
% We call a double auction rule {\em non-discriminating} if the price paid by all trading buyers is the same, and the price paid to all trading sellers is the same (but we do not require that the buyers price will be the same as the sellers price as in a uniform priced auction). 

After setting the trade quantity to the optimal trade quantity, most real markets proceed by choosing
a market clearing price anywhere in $[S_l,B_l]$. For example setting the price at $(B_l+S_l)/2$ -- ``the 1/2-Double Auction'' which is a special case of {\bf The k-Double Auction}~\cite{wilson85incentive,chatterjee83bargaining,satterthwaite89bilateral}. In general, the k-Double Auction is a double auction in which before the auction begins, a parameter $k$ is chosen such that $k\in \lbrack 0,1 \rbrack $. $k$ is used to calculate a clearing price $P=k\cdot S_l + (1-k)\cdot B_l$. $l$ units of the good are traded at the uniform price of $P$ for both sellers and buyers.
This pricing scheme is {\em not} incentive compatible (in dominant strategies),
but with additional strong assumptions on the agents values (all from a known 
distribution), 
it has been shown to perform reasonably well in many cases under 
strategic behavior of the 
participants~\cite{RusSatWill1994,mark-satterthwaite}. 
Nevertheless, even when assuming a uniform distribution of the agents values, 
there is a non zero efficiency loss in the Bayesian Nash equilibrium achieved 
(and this equilibrium concept is much weaker than the dominant strategies 
equilibrium we discuss in this paper).

One may alternatively use {\bf The VCG Double Auction} rule, which also sets 
the trade quantity to the optimal trade quantity $l$. This rule 
is non-discriminating, $l$ winning buyers pay $p_B = max(S_l, B_{l+1})$ 
and $l$ winning sellers receive $p_S = min(S_{l+1},B_l)$. 
VCG mechanisms \cite{Vic61,Cla71,Gro73} in general, and the VCG DA 
mechanism as a special case, are all IR and IC.
Incentive compatibility leads to maximal efficiency since 
the trade is of the optimal size $l$, but it also leads to a budget deficit 
since $p_B \le p_S$. By Observation~\ref{obs:single-payment}
any normalized, IC and efficient mechanism must have the same payments as the 
VCG DA and thus the mechanism is not budget-balanced.

%It is well known that as long as individual rationality or ``participation constraints'' are met (e.g. if non-traders pay 0) every
%incentive compatible mechanism that always achieves the optimal trade quantity
%must lead to a budget deficit.  We demonstrate several incentive
Myerson and Satterthwaite~\citeyear{Myerson83} have shown that as long as 
individual rationality or ``participation constraints'' are met (e.g. if 
non-traders pay 0),
an incentive compatible mechanism that always achieves the efficient outcome
 lead to a budget deficit (even for more general model and weaker solution 
concept that we consider).
%  (For more general model and solution concepts).  
We now turn to look at several normalized and IC double auction rules that 
achieve budget balance (sometimes even surplus) at the price of achieving 
slightly sub-optimal efficiency (by reducing the trade quantity).
%Here we only describe the rules shortly, more details can be found in appendix~\ref{appendix - DA rules}.

The simplest auction with this property is {\bf The Trade Reduction (TR) DA}.
% ~\cite{mcafee92dominant}. 
In this non-discriminating auction, $l-1$ units of the good are traded. 
Each trading buyer pays $p_B = B_l$, and each trading seller receives 
$p_S = S_l$. Since $B_l\ge S_l$ this auction is BB.
A rule which is an extension of the Trade Reduction DA rule, 
was previously suggested by McAfee~\citeyear{mcafee92dominant}.
By {\bf McAfee's DA} rule, if a suggested clearing price $p = {S_{l+1}+B_{l+1} \over 2}$ is accepted by the $l$ buyer and seller (${p\in \lbrack S_l,B_l\rbrack}$) then $l$ units of the good are traded at the price of $p$, otherwise the TR rule is used.  
Both the Trade Reduction DA rule and McAfee's rule are normalized, bid monotonic and the 
payments are by the critical values, thus they are IC (and IR) by applying 
Theorem~\ref{critical values - Incentive Compatible}.
Both rules have efficiency of at least $(l-1)/l$ for any agents values, 
since only the unit with the lowest trade value might not be traded.
McAfee's rule turned out not to be compatible with our protocols  -- 
we expand on this in appendix~\ref{Appendix - McAfee's chain auction}.  

We suggest two new normalized and randomized double auctions, 
which capture the tradeoff 
between the auction efficiency and the budget balance with one parameter 
$\alpha$. 
Unlike McAfee's rule, these rules can be used with our supply-chain protocols,
 and they achieve higher efficiency than the Trade Reduction DA in expectation.
For a carefully chosen parameter $\alpha$ they also achieve exact budget 
balance (zero balance) on expectation (Ex ante Budget-Balanced).

In {\bf The $\alpha$ Reduction DA}, 
% before the auction begins, a parameter $\alpha$ is chosen such that $\alpha\in \lbrack 0,1 \rbrack $. Then 
for a fixed $0\le \alpha\le 1$,
the bids are submitted and then with probability $\alpha$ the Trade Reduction 
DA rule is used, and with probability $1-\alpha$ the VCG DA rule is used. 
This randomized double auction is {\em universally incentive compatible} 
~\cite<defined by>{nisanalgorithmic}, 
% (defined by Nisan and Ronen~\citeyear{nisanalgorithmic}), 
which means that the 
agents bid truthfully even if they know the randomization result. 
% So this auction has an Ex-Post individual rationality property, in which agents never regret bidding truthfully even after knowing the auction results.
This can be seen from the fact that bidding truthfully is a dominant strategy 
in both the Trade Reduction DA rule and the VCG DA rule.
It is also normalized and ND since both Trade Reduction DA and VCG DA are normalized and ND. 

{\bf The $\alpha$ Payment DA} is another randomized double auction which has the same distribution of the allocation as the former auction (and therefore the same expected efficiency), but the payment of each agent is his expected payment of The $\alpha$ Reduction DA (so the expected budget of both auctions is the same). 
In this auction, a parameter $\alpha$ is chosen as in the $\alpha$ Reduction DA. Then the bids are submitted and the allocation and payments are decided. $l-1$ units are traded between buyers, each paying $\alpha\cdot B_l+(1-\alpha )\cdot max(B_{l+1}, S_{l})$, and the sellers, each receiving $\alpha\cdot S_l+(1-\alpha )\cdot min(S_{l+1}, B_{l})$. With probability $\alpha$ another unit of the good is traded between the $l$ buyer which pays $max(B_{l+1}, S_{l})$ and the $l$ seller which receives $min(S_{l+1}, B_{l})$.
This auction is discriminating since the $l$ buyer pays a different price than the rest of the 
winning buyers if he wins the auction (and the same holds for the sellers).
The $\alpha$ Payment DA has a much lower variance in most of the agents
 payments than the $\alpha$ Reduction DA, 
and it ``hides'' its randomized character from almost all the agents. 
The allocation and payment of all agents but the $l$ 
buyer and seller are independent of the coin toss, thus have zero variance.
This auction is individually rational and 
incentive compatible; but not universally.

\begin{theorem}
The $\alpha$ Payment DA is an incentive compatible randomized DA, 
but it is not a universally incentive compatible randomized DA.
\end{theorem}
\begin{proof}
Since the $\alpha$ Reduction DA is universally incentive compatible, truth telling maximizes the expected utility of any agent in the $\alpha$ Reduction DA. The $\alpha$ Payment DA has the same probability distributions of the allocation and payments as the $\alpha$ Reduction DA, therefore truth telling maximizes the expected utility of any agent in the $\alpha$ Payment DA as well.

The $\alpha$ Payment DA is not a universally incentive compatible randomized DA. 
Assume that a seller which is one of the first $l-1$ sellers knows that the 
randomization will result in a VCG allocation, 
so he is now facing a deterministic auction. 
By Observation~\ref{obs:single-payment} there is a unique payment rule which ensures dominant strategy IC for normalized mechanism with the efficient allocation (the VCG allocation), this is the VCG payment rule.
% It is known that the only payment rule which ensures dominant strategy incentive compatibility and individual rationality with a VCG allocation is the VCG payment rule. 
The $\alpha$ Payment DA is normalized and gives a different payment to that 
agent, therefore it cannot be incentive compatible in dominant strategies.
\end{proof}

Both auctions have efficiency of at least $(l-1)/l$, since at least $l-1$ of
the $l$ units are traded.
As $\alpha$ grows from zero to one, 
% the probability of trade reduction increases, and as a result 
the expected revenue increases from negative to positive and the expected 
efficiency decreases (linearly). 
%The VCG auction has revenue deficit and the Trade Reduction auction has revenue surplus, so 
If the distribution $D$ of the agents values is known prior to the beginning 
of the auction, the parameter $\alpha = \alpha(D)$ can be chosen such that 
the expected revenue is zero (different 
distributions have different values of $\alpha(D)$, in this paper we do not 
solve the
problem of finding $\alpha(D)$ analytically). We denote this value as 
$\alpha^\ast(D)$.
For the uniform distribution of agents values in $[0,1]$ we denote this 
value as $a^\ast$.

In Table~\ref{Double Auction Rules} we present a summary of the properties of 
the double auction rules. 
% Further details appear in ~\cite{BabaioffThesis}.

\input{DA_rules.tex}

We have run simulations comparing
the different DA rules with respect to the market revenue ($\sum_{i} p_i$) 
and to the total social efficiency ($\sum_{i\in A} v_i$). 
%In Figure~\ref{Sim b25 s25} and Figure~\ref{Sim b50 s5} 
In Figures~\ref{Sim b25 s25} and~\ref{Sim b50 s5} 
we show the results for the average of 100 random executions of an auction 
with a given number of buyers and sellers, 
with all values drawn uniformly and independently at random in $[0,1]$.
We have calculated the $\alpha$ Reduction DA efficiency to revenue ratios 
for $\alpha\in \{0.25,0.5,0.75\} $. 
Note that in expectation, the same results would have been obtained for the 
$\alpha$ Payment DA, since it has  
the same expected efficiency and revenue as the $\alpha$ Reduction DA.
We have calculated $a^\ast = \alpha^\ast(U)$ (where $U$ is the uniform 
distribution of agents values in $[0,1]$) by simulations using binary search.
Note that in both figures, the values of the Trade Reduction DA, the different $\alpha$ Reduction DA, the VCG DA as well as the $a^\ast$ Reduction DA, all lay on a linear curve. 
The point representing McAfee's DA lays above this line and in both 
simulations has lower efficiency than the $a^\ast$ Reduction DA.
Our $a^\ast$ Reduction DA extracts more efficiency than McAfee's DA, while still being budget balanced.
The simulations also show that in the symmetric case where the number of buyers and 
sellers is the same, all auctions extract a very high fraction of the efficiency (more than 99\%). 
On the other hand in the asymmetric case where the number of buyers is much larger than the number of sellers, the Trade Reduction DA as well as McAfee's DA extract a significantly lower efficiency
than the $a^\ast$ Reduction DA (about 5\% less).

%\begin{figure}[htb]
%\centerline{\resizebox{!}{8cm}{\includegraphics{Sim_b25_s25.eps}}}
%\caption[]{\label{Sim b25 s25} Simulations results with 25 buyers and 25 sellers}
%\end{figure}

%\begin{figure}[htb]
%\centerline{\resizebox{!}{8cm}{\includegraphics{Sim_b50_s5.eps}}}
%\caption[]{\label{Sim b50 s5} Simulations results with 50 buyers and 5 sellers}
%\end{figure}


\begin{figure}[htb]
\centerline{\resizebox{!}{8cm}{\includegraphics{Sim_b25_s25.eps}}}
\caption[]{\label{Sim b25 s25} 25 buyers and 25 sellers}
\centerline{\label{Auctions simulations results1} Revenue/Efficiency tradeoff simulations results}
\end{figure}

 \begin{figure}[htb]
\centerline{\resizebox{!}{8cm}{\includegraphics{Sim_b50_s5.eps}}}
\caption[]{\label{Sim b50 s5} 50 buyers and 5 sellers}
\centerline{\label{Auctions simulations results2} Revenue/Efficiency tradeoff simulations results}
\end{figure}

\cout{

\begin{picture}(400,220)
\put(-40,25){\psfig{figure=Sim_b25_s25.eps,height=5.8cm}}
\put(-40,10){\makebox(200,220)[b]{25 buyers and 25 sellers}}
\put(160,25){\psfig{figure=Sim_b50_s5.eps,height=5.8cm}}
\put(160,10){\makebox(200,220)[b]{50 buyers and 5 sellers}}
\centerline{\label{Auctions simulations results} Revenue/Efficiency tradeoff simulations results}
\end{picture}

} %cout

% ---------------------------------------------------------------------------

%%%\pagebreak
\section{The Supply Chain Protocols}
\label{The protocols}
% NEW PART: Model
We begin by presenting the linear supply chain model, in which any unit 
of an initial good can be converted to a unit of the final good through a 
sequence of unit to unit conversions. 
% (in order to simplify the analysis, in this section we assume that each agent bids for a single unit only, in Section~\ref{Multi-Unit Bids} we briefly discuss extending it to multi-unit bids).
Our supply chain model is a single-minded agents model with the following 
% additional restrictions. 
specifications of possible outcomes, value spaces and classes of agents.
There is an ordered set $G$ ($|G|=t$) of homogeneous goods that are traded in 
discrete quantities. Each agent $i$ is of one of the following $t+1$ classes. 
An {\em initial supplier} can supply one unit of the first good and has 
a non-negative cost $s_i$ ($v_i = -s_i$) if he trades.
A {\em converter} of one unit of good $r\in \{1,\ldots,t-1\}$ 
to one unit of good $r+1$ has a non-negative cost $s_i$ ($v_i = -s_i$) if he 
converts a unit.
A {\em consumer} has a non-negative value $b_i$ ($v_i = b_i$) if he receives one unit of the final good.
A {\em market} is the set of agents of the same class.
The allocation $A$ is {\em materially balanced} if for each good, 
the number of units produced is the same as the number of units consumed. This means that the number of winners of any class of agents is the same. 
% This means that for any good the number of items manufactured is the same as the number of items consumed. 
Clearly the number of winners in any market cannot exceed the minimal number 
of bidders in any market $n$,
% Since the size of trade cannot exceed the minimal number of agents in any market, 
so we can assume that all markets have only $n$ bidders
($n$ can be found by a single message between any market 
and the next market. The message includes the minimal size seen so far. 
The consumer market then sends $n$ backwards in the chain to all other markets).

%Similar to the DA model, we assume that each agent $i$ has a {\em valuation function} 
%$V_i$ over the outcomes of the auction, and that agents have no externalities. 
%Let $A$ be the allocation of the auction, which is the set of trading agents.
%Agent $i$'s assign a real {\em value} $v_i$ for allocation $A$ if $i\in A$, 
%and $0$ if $i\notin A$.
%% For any agent $i$, if $i\notin A$ then $i$ values the outcome with 0.
%An initial supplier $i$ has a non-negative cost $s_i$ ($v_i = -s_i$) if he 
%sells his unit of the initial good.
%Converter $i$ has a non-negative cost $s_i$ ($v_i = -s_i$) if he convert one 
%unit of his input good to one unit of his output good.
%Consumer $i$ has a non-negative value $b_i$ ($v_i = b_i$) if he receives one 
%unit of the final good.
%If agent $i$ pays $p_i$, his {\em utility} is $u_i(A) = V_i(A) - p_i$ 
%(note that suppliers and converters pay non-positive payment if they trade, 
%which means that they receive money). 
%We assume that agents are self-interested and try to maximize their utility. 
%The allocation $A$ is {\em materially balanced} if for any good the number of 
%items manufactured is the same as the number of items consumed. 
%The allocation $A$ is {\em efficient} if $\sum_{i\in A} v_i$ is maximized,
%and the auction is {\em budget balanced} if $\sum_{i} p_i \ge 0 $.

We suggest two protocols that can be used to conduct an auction in a chain of markets in a distributed manner: {\bf The Symmetric Protocol} and {\bf The Pivot Protocol}. Both protocols run on servers connected by a network with a linear chain topology. 
Each server represents one market and receives bids from only one class of agents (suppliers, consumers or converters from some specified good to the next good in the chain). The servers do not act strategically, and follow the specified protocols (they are all owned by the same entity). 

We denote the supply market as $M^1$ and each conversion market from a good $r$ to the following good $r+1$ as $M^{r\to r+1}$. The consumer (demand) market is marked by $M^t$. Each of the conversion markets is connected with bi-directional communication channels to the market that supplies its input good and to the market which demands its output good. We denote the supply and demand curves for a good $r$ as $S^r$ and $D^r$ respectively, and the supply and demand curves for the conversion of a good $r$ to a good $r+1$ as $S^{r\to r+1}$ and $D^{r\to r+1}$ respectively. 

All agents must bid before some fixed deadline. The input to our protocols is the supply 
bids for the first good, the conversion bids for all the conversion markets and the demand bids 
for the final good.
The protocols decide the allocation and the payments of the trading agents 
(the protocols are normalized, losing agents pay zero).
Both our protocols are generic and can operate with various normalized DA 
rules.

In the Symmetric Protocol, each of the markets conducts a double auction, 
after constructing its demand and supply curves. 
Each agent views the supply chain auction as a double auction 
since each market conducts a double auction and there is no central 
market that makes the allocation and payments decisions. 
In order for the protocol to create a materially balanced
 allocation, some restriction are imposed on the double auction rule used by 
the Symmetric Protocol, as we later describe.
This protocol can use either a discriminating or a non-discriminating DA rule.
We present the protocol as using an abstract discriminating DA rule that 
takes supply and demand curves as inputs, 
and returns the trade quantity $q$ and 
two price vectors, $\vec{P}_S$ for the sellers and $\vec{P}_B$ for the buyers.

In the Pivot Protocol, only one market (the demand market) constructs its 
demand and supply curves, this market applies the double auction allocation 
and payments rule, and sends the results of the auction to it predecessor.
Each market uses the information it receives and the bids in the market to
send its predecessor information that are used to calculate its allocation 
and payments.
Unlike the Symmetric Protocol, the Pivot Protocol must use a 
non-discriminating DA rule, 
but it creates a materially balanced allocation with any DA rule. 
For many DA rules, this protocol can be improved such that it has a much lower 
communication burden than the Symmetric Protocol, as we show in 
Section~\ref{Communication Complexity}.
We present the protocol as using an abstract non-discriminating double auction
 rule that takes supply and demand curves as inputs, and returns the trade 
quantity $q$ and a single price $P_S$ for the trading sellers and another 
price $P_B$ for the trading buyers.

% Before presenting the protocols in details, we characterize incentive
% compatible supply chain mechanisms.

\subsection{The Symmetric Protocol}
\label{The Symmetric Protocol}
As we have seen in the example in Section~\ref{The Lemonade-stand industry}, 
after the bids are submitted the Symmetric Protocol begins with supply curve 
propagation along the supply 
chain, from the supply market to the consumer market. 
The protocol continues with demand curve propagation along the supply chain 
in the other way (demand curves propagation may be done concurrently with 
the supply curves propagation). 
%(Any market that receives a curve longer then its curve, shorten it to match its curve length).
During this process each of the markets builds its supply and demand curves 
from the information it receives. At this point each of the markets has its 
supply and demand curves, and a double auction is conducted. 
% If the rule is randomized, the random choice is shared between the markets. 
If the rule is randomized, we assume that the random coins are public,
which means that all markets have access to the same random coins (a public 
coin is created by one market tossing the coin and then propagating the 
result to all other markets along the supply chain).
The formal protocol for the supply market $M^1$, the conversion markets
$ \convmarket{r} $ and the demand market $M^t$ are described in 
Figures~\ref{Symmetric Protocol for the Supply Market},
~\ref{Symmetric Protocol for a Conversion Market }  and 
~\ref{Symmetric Protocol for the Demand Market}, respectively.

%% The formal protocol for the supply market $M^1$ is described in 
%% figure~\ref{Symmetric Protocol for the Supply Market}. 
%% The formal protocol for the 
%% conversion markets is described in 
%% figure~\ref{Symmetric Protocol for a Conversion Market } 
%% and the formal protocol for the demand market $M^t$ is described in 
%% figure~\ref{Symmetric Protocol for the Demand Market}. 
% ----------------------------------------------------------------------------
% \pagebreak
\begin{figure}[]
\centering
\fbox{\small
% \fbox{\tiny
% \hsize = 2in
% \font{10pt}
\begin{minipage}{12cm}

\begin{tabbing}

(x) \= \kill

{\bf Symmetric Protocol for the Supply Market $ M^1 $.} \\[3mm]
\> 1. $ S^1 \leftarrow$ sort the list of supply bids in non-decreasing order. \\[1mm]
\> 2. Send $S^1$ to demand market $ M^{1\to 2}$. \\[1mm]
\> 3. Receive $D^1$ from demand market $ M^{1\to 2} $. \\[1mm]
% \> 4. $(q, P_S, P_B) \leftarrow$ DA Rule($S^1, D^1$). \\[1mm]
\> 4. Apply the DA Rule on $(S^1, D^1)$ to obtain $(q, \vec{P}_S, \vec{P}_B)$. \\[1mm]
\> 5. Output: The $q$ lowest bidders sell a unit each and pay by the vector $\vec{P}_S$.  \\[1mm]
\end{tabbing}
\end{minipage}

}
\caption[]{\label{Symmetric Protocol for the Supply Market} Symmetric Protocol for the Supply Market}
\end{figure}
% \pagebreak

% ---------------------------------------------------------------------------- 
% \pagebreak
\begin{figure}[]
\centering
\fbox{\small
\begin{minipage}{12cm}

\begin{tabbing}

(x) \= \kill

{\bf Symmetric Protocol for a Conversion Market $ \convmarket{r} $ }\\[3mm]
\> 1. $ \gconv{S}{r} \leftarrow$ sort the list of supply bids in non-decreasing order. \\[1mm]
\> 2. When receiving $S^r$ from  $ M^{r-1\to r} $ , \\[1mm]
\> \ \ \ \ \ send $S^{r+1} = S^r + \gconv{S}{r} $ to $ M^{r+1\to r+2} $. \\[1mm]
\> 3. When receiving $D^{r+1}$ from $ M^{r+1\to r+2} $, \\[1mm]
\> \ \ \ \ \ send $D^{r} = D^{r+1} - \gconv{S}{r} $ to $ M^{r-1\to r} $. \\[1mm]
\> 4. Construct the market demand curve $ \gconv{D}{r} =  D^{r+1} - S^r $.\\[1mm]
\> 5. Apply the DA Rule on ($\gconv{S}{r}, \gconv{D}{r}$) to obtain $(q, \vec{P}_S, \vec{P}_B)$. \\[1mm]
\> 6. Output: The $q$ lowest bidders convert a unit each and pay by the vector $\vec{P}_S$.   \\[1mm]

\end{tabbing}
\end{minipage}

}
\caption[]{\label{Symmetric Protocol for a Conversion Market } Symmetric Protocol for a Conversion Market }
\end{figure}
% \pagebreak

% ----------------------------------------------------------------------------
% \pagebreak
\begin{figure}[]
\centering
\fbox{\small
\begin{minipage}{12cm}

\begin{tabbing}

(x) \= \kill

{\bf Symmetric Protocol for the Demand Market $ \demmarket $ }\\[3mm]
\> 1. $ D^t  \leftarrow$ sort the list of demand bids in non-increasing order. \\[1mm]
\> 2. Send $D^t$ to supply market $ M^{{t-1}\to t} $.\\[1mm]
\> 3. Receive $S^t$ from supply market $ M^{{t-1}\to t} $. \\[1mm]
\> 4. Apply the DA Rule on ($S^t, D^t$) to obtain $(q, \vec{P}_S, \vec{P}_B)$. \\[1mm]
\> 5. Output: The $q$ highest bidders buy a unit each and pay by the vector $\vec{P}_B$.  \\[1mm]
\end{tabbing}
\end{minipage}

}
\caption[]{\label{Symmetric Protocol for the Demand Market} Symmetric Protocol for the Demand Market}
\end{figure}
% \pagebreak


% ---------------------------------------------------------------------------- 

%Since we require {\em material balance}, which means that every conversion market produces the 
%same number of items as it consumes, we require that all markets decide on the same trade size.
% A double auction rule with this property is called {\em consistent}.
A DA rule decides on the trade size in each market according to the supply and demand curves 
created by the protocol. The allocation is materially balanced only in the case that 
the same trade size was decided in all the markets.

\begin{definition}
Let $S(M)$ and $D(M)$ be the supply and demand curves created by the Symmetric Protocol 
in market $M$.
Let $q(M)$ be the trade size obtained by applying the DA rule $R$ on $(S(M), D(M))$.
A DA rule $R$ is called {\bf consistent} if $q({M1}) = q({M2})$ for any two markets $M1$ and $M2$.
\end{definition}

The following Lemma shows that the optimal trade size in all markets is the 
same, so any rule that set the trade size as function of the optimal trade size is consistent.
\begin{lemma}
Let $l(M)$ be the optimal trade size in market $M$.
For any two markets $M1$ and $M2$, $l({M1}) = l({M2})$. 
We denote this optimal trade size by $l$.
\end{lemma}
\begin{proof}
By the definition of the optimal trade size, $l(M)$ is the maximal index such that 
 $B_{l(M)}(M)\ge S_{l(M)}(M)$. 
It is enough to show that for any two markets $M1$ and $M2$, 
$B(M1) - S(M1) = B(M2) - S(M2)$ (as vectors).

For any $r$:

$ D^{r\to r+1} - S^{r\to r+1} = 
(D^{r+1} - S^{r}) - S^{r\to r+1}=
(D^t - \sum_{m=r+1}^{t-1} S^{m\to m+1}) - S^{r} - S^{r\to r+1} = \\ 
D^t - ( S^{r} + S^{r\to r+1} + \sum_{m=r+1}^{t-1} S^{m\to m+1} )=
D^t - S^t $  

Similar argument shows that $D^1 - S^1 = D^t - S^t $
\end{proof}

We conclude that if the trade size $q_M$ decided by DA rule $R$ in any market $M$ is just
 a function of the optimal trade size $l_M = l$, then $R$ is consistent. 
Clearly a consistent DA rule always creates a materially balanced allocation.

Since the trade size decided by the VCG DA rule is $l$, then this rule is consistent.
Similarly the Trade Reduction DA rule is consistent since the trade size is $l-1$.
Not all double auction rules are consistent, 
McAfee's DA  is an example for an inconsistent rule (a specific example
of inconsistency is presented in appendix~\ref{Appendix - McAfee's chain auction}). The intuitive reason 
that it is not consistent is because the trade size is dependent on the comparison between 
some function of the $l+1$ bids and the $l$ bids, which might be different between markets.
On the other hand our two new randomized DA, the $\alpha$ Reduction DA and the $\alpha$ Payment DA
are consistent. This is because all markets share a public coin, so either the trade size is $l-1$ 
in all the markets, or it is $l$ in all the markets.

% For example the VCG rule and the Trade Reduction rules are consistent since the trade size is $l$ and $l-1$ respectively.


% The following theorem 
% In case that the double auction rule is consistent and incentive compatible, the symmetric protocol creates an incentive compatible mechanism:
Following is the main theorem regarding the Symmetric Protocol.
\begin{theorem}
\label{symmetric protocol is incentive compatible} 
Any normalized DA rule $R$ that is consistent can be used by the 
Symmetric Protocol to create a supply chain mechanism that is normalized and
materially balanced.
If $R$ is also IC then the mechanism created by the Symmetric 
Protocol is IC (thus also IR) and its efficiency is the efficiency of $R$. 
If $R$ is also non-discriminating, then the mechanism is also 
non-discriminating.
\end{theorem}
\begin{proof} 
Since $R$ is consistent the allocation is materially balanced by definition.
The payments are normalized by definition, we show that if $R$ 
is IC then the mechanism is also IC.
By Theorem~\ref{critical values - Incentive Compatible} the DA rule $R$ 
is bid monotonic and the payments are by critical values.
For any agent, the supply and demand curves (disregarding his bid) are
 independent of his bid by the way they are built by the protocol.
So the mechanism is bid monotonic and the payments are by critical values 
(from the agent point of view, he submits his bid to a DA), therefore
by the other direction of Theorem~\ref{critical values - Incentive Compatible} 
the supply chain mechanism is IC (and IR). 
By IC and the way that costs are aggregated by the
protocol, the efficiency of the mechanism is the same as the efficiency of $R$.
%We show that if the DA rule $R$ is IC then any agent in the supply chain bids 
%truthfully.
%For any agent, the supply and demand curves (disregarding his bid) are
% independent of his bid by the way they are built by the protocol.
%Therefore from the agent point of view, he submits his bid to an IC double 
%auction, so he cannot increase his utility by bidding untruthfully.
%Since all the agents bid truthfully then the mechanism created by the 
%symmetric protocol is IC.  
%Similar argument shows that since $R$ is IR, the mechanism is also IR.
If the $R$ is non-discriminating, then the payments of all the winning agents 
in the any market are the same, so the mechanism is non-discriminating. 
\end{proof}

Note that the same normalized, IC and consistent DA rule must be used in all 
the markets for the mechanism to be materially balanced, normalized and IC.
The DA rule is just a function of the supply and demand curves in the market.
If any two of the supplier and conversion markets get the same supply bids, 
they also get the same demand curves so for consistency both must have the same
allocation. Since both are normalized and IC by 
Observation~\ref{obs:single-payment} both must also have the same payment rule.
The demand market must have the same DA rule as the 
supply market, since in the case that all converters have a zero cost, both 
markets have the same supply and demand curves. Applying the same argument 
presented above to these markets, proves that they must have the same DA rule.

% ---------------------------------------------------------------------------- 
\subsection{The Pivot Protocol}
% As we have seen in the example in Section~\ref{The Lemonade-stand industry}, 

The Pivot Protocol is a supply chain protocol that creates a normalized 
materially balanced supply chain mechanism from any non-discriminating 
normalized double auction rule. 
If the DA rule is also incentive compatible then the protocol creates an 
incentive compatible supply chain mechanism.
% The protocol is designed to create a normalized incentive compatible supply 
% chain mechanism from any normalized DA rule that is non-discriminating and 
% incentive compatible.
Unlike the Symmetric Protocol, the Pivot Protocol is not 
restricted to using consistent double auction rules, so in that sense it is
less restricted than the Symmetric Protocol.
On the other hand, unlike the Symmetric Protocol it is restricted to use
non-discriminating double auction rules. 
The use of randomized double auctions is also more natural in the Pivot 
Protocol, since only one market (the Pivot market) uses the random coins and 
there is no need for public coins created by distribution of the random coins 
of one market to all other markets.

% If the DA rule is both consistent and non-discriminating, then both protocols create the same mechanism.  

Before defining the Pivot Protocol formally, we explain its execution on 
the Lemonade-stand industry example of Section~\ref{The Lemonade-stand industry}.
As in the Symmetric Protocol, the protocol begins with supply curve 
propagation along the supply chain to the juice market (see Figure~\ref{example1b table}). 
Figure~\ref{example4a table} presents the information propagation of 
the Pivot Protocol after the supply curve propagation stage, 
and is explained below. 
\input{table4a.tex}

Unlike in the Symmetric Protocol, the demand curve is not propagated backwards, 
but rather, the juice market, which has its supply and demand curves at that 
stage, now conducts a non-discriminating double auction.
For example, running the VCG double auction results with efficient trade 
of size $2$ in the juice market.
This trade size is propagated to all other markets and is 
set to be the trade size in each market along the supply chain, 
ensuring a materially balanced allocation (the trade size 
is denoted by $q$ in Figure~\ref{example4a table}). 
The VCG DA rule charges the two winning consumers in the 
juice market for $ \$9 = max(\$9,\$7) $ each (since they must bid at least
\$9 to match the supply of juice, and if they do, they also defeat Cindy, the 
losing consumer). 
There is no single agent that has a juice supplier role in the juice market, 
rather, a ``juice supplier'' is an aggregation of a lemon picker and a juice squeezer.
We use the price that the double auction would have charged a supplier in 
the juice market to find the prices for lemon pickers and juice squeezers. 
Each market sends to it predecessor in the chain the highest price the winning
agents are willing to pay for one unit of the input good.
A ``supplier'' in the juice market should be paid $ \$11 = min(\$13, \$11)$,
the maximal cost a winning supplier can charge for juice. 
So, \$11 is the highest cost for juice, and the juice market informs the 
squeezing market that the trade size is $2$ and that the price of juice 
should not exceed \$11 ($V$ in the figure marks this propagated value).
The squeezing market informs the lemon market that the trade size is $2$ and
that the price in the lemon market should be at most $\$8 = \$11- \$3 $, 
since the highest cost of a winner in the squeezing market is \$3. 
The price in the squeezing market cannot exceed $ \$5 = \$11 - \$6 $, since 
the price of juice cannot exceed \$11 and the cost of lemon for a 
winning lemon picker might be as high as \$6.
Also, the price in the squeezing market cannot exceed \$6, the cost of the 
loser in that market, so the price is set to $\$5 = min (\$6, \$5)$. 
The price in the lemon market is set to $\$7 = min (\$7, \$8)$, 
since the price cannot exceed \$7, the cost of the loser in that market, which
is lower than the propagated maximal cost of \$8.

Note that when we use the VCG double auction rule, the Lemonade-stand industry 
allocation and payments of the Pivot Protocol are exactly the same as
the allocation and payments of the Symmetric Protocol presented in Section~\ref{The Lemonade-stand industry}. We later show (Theorem~\ref{pivot protocol and symmetric protocol equivalence}) that this is a general phenomena which happens for any normalized DA incentive compatible rule that can be used by both protocols, that is, a DA rule that is non-discriminating and consistent 
% this is the only case the DA rule can be used by both protocols. 
(if the DA rule is inconsistent, like the McAfee's DA rule, 
the allocation created by the Symmetric Protocol is not materially balanced. 
If on the other hand the rule is discriminating, 
it cannot be used by the Pivot Protocol since there are different maximal unit
costs for different winning agents in the same market).
% (the example presented in Appendix~\ref{Appendix - McAfee's chain auction} shows that this might not be the case if the rule is inconsistent, like McAfee's DA rule).


%The Pivot Protocol is a supply chain protocol that is more generic than 
%the Symmetric Protocol in one aspect, since it can work even with DA rules 
%that are not consistent. 
%It is less generic in another aspect, since it must use a non-discriminating 
%DA rule.

We now turn to the general definition of the Pivot Protocol.
In the Pivot Protocol, one of the markets is chosen as a pivot and the
double auction is only held there. 
Any market may be chosen as a pivot; we describe the case where the pivot is 
the consumer market.
After all bids are submitted, the protocol begins with supply curves 
propagation along the supply chain as in the Symmetric Protocol. 
At this point the consumer market has its supply and demand curves, 
and a non-discriminating double auction is conducted in this market.
The DA sets the trade size, the price the mechanism charges the consumers, 
and the highest cost of a unit of the good (supplier's price), 
which is sent to the predecessor market of the consumer market.
After that, starting with the consumer market which is now viewed as the 
demand market of its predecessor, each of the demand markets sends to its 
supply market the size of trade and the highest price that the demand market 
is willing to pay for one unit of its input good, without reducing the trade 
quantity.
The payment in each market is set to the maximal cost in each market that 
results with the same trade size, and is calculated as the minimum of 
two terms. 
The first term is the difference between the propagated maximal cost of the 
market output and the maximal cost of the market input.
The second term is the highest cost of a loser in that market.   
% 111111111111111 add that this is not the payment!!!!!!!!!
We show below that this payment scheme 
creates a normalized, incentive compatible and non-discriminating supply chain
mechanism, given a normalized, incentive compatible and non-discriminating 
double auction rule.

The formal protocol for the pivot market, the conversion markets and the 
supply market are presented in Figures~\ref{Pivot Protocol},~\ref{Pivot Protocol for a Conversion Market} and~\ref{Pivot Protocol for the Supply Market}, respectively.

% The protocol for the pivot market is described in figure~\ref{Pivot Protocol}. The protocol for the conversion markets is described in figure~\ref{Pivot Protocol for a Conversion Market} and the protocol for the supply market is described in figure~\ref{Pivot Protocol for the Supply Market}.

% ----------------------------------------------------------------------------
% \pagebreak
\begin{figure}[]
\centering
\fbox{\small
\begin{minipage}{12cm}

\begin{tabbing}

(x) \= \kill

{\bf Pivot Protocol for Pivot Market $M^t$} \\[3mm]
\> 1. $ D^t  \leftarrow$ sort the list of demand bids in non-increasing order. \\[1mm]
\> 2. Receive $S^t$ from supply market $ M^{{t-1}\to t} $. \\[1mm]
\> 3. apply DA Rule on ($S^t, D^t$) to obtain $(q, P_S, P_B)$. \\[1mm]
\> // Send results to the other markets:  \\[1mm]
\> 4. Send $(P_S, q)$ to market $M^{t-1\to t}$. \\[1mm]
\> 5. Output: The $q$ highest bidders buy for price $P_B$.  \\[1mm]

\end{tabbing}
\end{minipage}

}
\caption[]{\label{Pivot Protocol} The Pivot Protocol for Pivot Market }
\end{figure}
% \pagebreak
% ---------------------------------------------------------------------------- 

% ----------------------------------------------------------------------------
% \pagebreak
\begin{figure}[]
\centering
\fbox{\small
\begin{minipage}{12cm}

\begin{tabbing}

(x) \= \kill

{\bf Pivot Protocol for a Conversion Market $ \convmarket{r} $} \\[3mm]
\> 1. $ \gconv{S}{r} \leftarrow$ sort the list of supply bids in non-decreasing order. \\[1mm]
\> 2. When receiving $S^r$ from  $ M^{r-1\to r} $ , \\[1mm]
\> \ \ \ \ \ send $S^{r+1} = S^r + \gconv{S}{r} $ to $ M^{r+1\to r+2} $. \\[1mm]
\> 3. When receiving the pair $(V,q)$ from $ M^{r+1\to r+2} $, \\[1mm]
\> \ \ \ \ \ send $(V-\gconv{S}{r}_q,q)$ to $ M^{r-1\to r} $. \\[1mm]
\> 4. Output: The $q$ lowest bidders sell for price $min(V-S^r_{q},\gconv{S}{r}_{q+1})$.  \\[1mm]
\end{tabbing}
\end{minipage}

}
\caption[]{\label{Pivot Protocol for a Conversion Market} Pivot Protocol for a Conversion Market}
\end{figure}
% \pagebreak
% ---------------------------------------------------------------------------- 

% ----------------------------------------------------------------------------
% \pagebreak
\begin{figure}[]
\centering
\fbox{\small
\begin{minipage}{12cm}

\begin{tabbing}

(x) \= \kill

{\bf Pivot Protocol for the Supply Market $ \supmarket $} \\[3mm]
\> 1. $ S^1 \leftarrow$ sort the list of supply bids in non-decreasing order. \\[1mm]
\> 2. Send $S^1$ to demand market $ M^{1\to 2}$. \\[1mm]
\> 3. Receive the pair $(V,q)$ from the demand market $ M^{1\to 2} $. \\[1mm]
\> 4. Output: The $q$ lowest bidders sell for price $min(V,S^1_{q+1})$.  \\[1mm]
\end{tabbing}
\end{minipage}

}
\caption[]{\label{Pivot Protocol for the Supply Market} Pivot Protocol for the Supply Market}
\end{figure}
% \pagebreak
% ---------------------------------------------------------------------------- 


% In the following theorem we prove that if the double auction rule used by the pivot market is incentive compatible and non-discriminating (which means that all winning agents of the same type pay the same price), then the Pivot Protocol creates an incentive compatible, non-discriminating mechanism.

The following theorem shows how the properties of the mechanism created by the Pivot Protocol are derived from the properties of the DA rule used by the pivot market.

\begin{theorem}
\label{pivot protocol is incentive compatible} 
Any normalized DA rule $R$ that is non-discriminating can be used by the 
Pivot Protocol to create a normalized supply chain mechanism that is 
materially balanced and non-discriminating.
If $R$ is also IC then the mechanism created by the 
Pivot Protocol is IC (thus also IR) and its efficiency is the 
efficiency of $R$.
% If the double auction rule used in the pivot market is incentive compatible and non-discriminating, then the mechanism created by the Pivot Protocol is incentive compatible and non-discriminating. 
\end{theorem}

\begin{proof}
From the protocol definition the mechanism is materially balanced, normalized 
and non-discriminating. 
Assume that the DA rule is normalized and IC.
% Since the DA rule in the pivot market is normalized and IC, and 
Then, since by the protocol definition the supply curve in the pivot market 
is independent of the bids of the consumers, 
the mechanism is normalized and IC for the consumers. 
We prove that it is IC for initial suppliers,
% We will prove that any seller in the supply market bids truthfully, 
the proof for the converters is similar (so it will be omitted), and we 
conclude that the mechanism is normalized and IC (thus also IR).
We show that the mechanism is bid monotonic and the payments are by critical 
values, thus by Theorem~\ref{critical values - Incentive Compatible} the 
mechanism is IC.

Assume supplier $i$ bids $S_i^1$ and wins. Assume the trade size is $q$ 
 ($q\ge i$ since $i$ wins) and $P_S$ is the price to the ``sellers'' in the 
pivot market.
The allocation is bid monotonic since if he bids a lower cost he is 
still one of the $q$ lowest bidding suppliers and his bid change can only 
reduce the cost of the $q$ lowest bidding sellers in the pivot market. 
By applying Lemma~\ref {lem:ND-price-fixed} on the DA rule, $P_S$ remains the 
same, and $i$'s corresponding seller bid is still lower than $P_S$ so he 
remains a winner. 
% Be Observation there 
Let $C_i^1$ be the critical value for supplier $i$.

% $X$ to the supply market $M^1$ and assume we then run 
% the pivot protocol using an IR, IC and ND double auction rule that results in 
% trade size $q$ and in $P_S$ being the payment to the ``sellers'' in the pivot 
% market. 
% If $i$ is a winner then he is one of the $q$ first suppliers, therefore
% if he bids higher (lower cost) he is still one of the $q$ highest suppliers and 
% his bid change can only improve the $q$ highest sellers bids in the pivot market. 
% By Lemma~\ref {lem:ND-price-fixed} his seller bid is above the sellers price in
% the pivot market, so he remains a winner.

By the Pivot Protocol the payment to a winning supplier in the supply 
market is 
$$
p_i^1 = min(P_S - \sum_{r=1}^{t-1} \cconv{q}{r}, S^1_{q+1}) 
$$
% We show that this is the critical value of supplier $S_i^1$.
% (payment by the critical value ensures incentive compatibility - see ~\cite{BabaioffThesis})

We need to show that $C_i^1 = p_i^1$ to prove that the payments are by 
critical values.
Assume that $i$ changes his bid to $X$ and he is now the $j$ bid in his market
under the new order of the bids. 
We show that if $X<p_i^1$ he wins and if $X>p_i^1$ he loses (note that here we consider costs, not values). 
This means that $p_i^1$ is the critical value for 
supplier $S_i^1$ to win the auction.
%  (note that both the trade size $q$ and the price $P_S$ might change). 
%We show that if $X < S^1_{q+1}$ and $X < P_S - \sum_{r=1}^{t-1} \cconv{q}{r}$ 
%then he wins, and if $X > S^1_{q+1}$ or 
%$X> P_S - \sum_{r=1}^{t-1} \cconv{q}{r}$ then he loses (this 
%also proves that the mechanism is bid monotonic).
\begin{itemize}
\item If $X < p_i^1$ then $X < S^1_{q+1}$ and 
the supplier is still one of the $q$ highest bidders in his market ($j\le q$).
By the way the protocol 
builds the supply curve in the pivot market, his bid change can only 
change the $q$ highest sellers bids in the pivot market.
All the $q$ highest sellers bids in the pivot market are still below $P_S$, 
since originally $S^1_{q} + \sum_{r=1}^{t-1} \cconv{q}{r}< P_S $, and even if 
he is the $q$ bidder by the assumption $X+ \sum_{r=1}^{t-1} \cconv{q}{r}< P_S $.
By Lemma~\ref {lem:ND-price-fixed} applied on the DA rule, $P_S$ remains the 
same and since $i$'s corresponding seller bid is below $P_S$, the supplier 
wins the auction.
This proves that $C_i^1 \ge p_i^1$

%\item If $X < S^1_{q+1}$ and $X< P_S - \sum_{r=1}^{t-1} \cconv{q}{r}$, then 
%the supplier is the $j$ in his market for $j\le q$. By the way the protocol 
%builds the supply curve in the pivot market, his bid change can only 
%improve the $q$ highest sellers bids in the pivot market. 
%By Lemma~\ref {lem:ND-price-fixed} $P_S$ remain the same and since 
%his seller bid is below $P_S$, the supplier wins the auction.
%\item If $X > S^1_{q+1}$, then he is not one of the $q$ first suppliers, so 
%for him to win the trade size must grow to $Q$ for $Q>q$. 
%But if this is so, by Lemma~\ref {lem:ND-price-fixed} and the way the supply
%curve in the pivot market is built, the trade size should remain $Q$ when 
%he bids $S_i^1$, which contradicts the assumption that it is $q$ when he bids
%$S_i^1$.
%\item If $X> P_S - \sum_{r=1}^{t-1} \cconv{q}{r}$ and $X < S^1_{q+1}$ then it 
%is impossible that the trade size is $q$ since $S^1_{q}\ge X$ and by the pivot
% protocol $ S^t_q = S^1_q + \sum_{r=1}^{t-1} \cconv{q}{r} $ and therefore 
%$ S^t_q \ge X + \sum_{r=1}^{t-1} \cconv{q}{r} > P_S $ which is a contradiction
% to the fact that the rule is incentive compatible and $S^t_q\le P_S$.

\item If $X > S^1_{q+1}$, then $j\ge q+1$.
For him to win when bidding $X$ it must be that 
$C_i^1 > X + \sum_{r=1}^{t-1} \cconv{j}{r}$, but
then $C_i^1 > S^1_{q+1} + \sum_{r=1}^{t-1} \cconv{q+1}{r}$ which by ND 
means that the original $q+1$ supplier (which is now the $q$ supplier) 
must win if $i$ bids $X$. 
By Lemma~\ref {lem:ND-price-fixed} the original $q+1$ supplier
 must also win if $i$ bids $S^1_{i}$ which contradicts the assumption 
that the trade size is $q$ when $i$ bids $S_i^1$.

%\item If $X > S^1_{q+1}$, then he losses the auction, since the trade size is 
%$q$ and he is not one of the first $q$ bidders in his market.

\item If $X> P_S - \sum_{r=1}^{t-1} \cconv{q}{r}$ and $X \le S^1_{q+1}$ then 
 $j\le q$ (without loss of generality he is ordered before the $q+1$ bid if 
there is a tie). 
Since $X + \sum_{r=1}^{t-1} \cconv{q}{r} > P_S $ and 
$P_S \ge S^1_{q} + \sum_{r=1}^{t-1} \cconv{q}{r}$ (the original $q$ supplier 
wins when $i$ bids $S^1_{i}$) we conclude that $X>S^1_{q}$ which means that 
he is now the $q$ bidder ($j=q$). So his corresponding seller bid in the DA is 
$X + \sum_{r=1}^{t-1} \cconv{q}{r}>P_S$, which is not high enough to win the 
DA and therefore the agent loses.

\end{itemize}
We conclude that any agent which wins the auction pays his critical value, 
and therefore the auction is IR and IC. By IC and the way that costs are 
aggregated by the protocol, the efficiency of the mechanism is the same as 
the efficiency of $R$.
% -----------------------------------
\end{proof}

% Theorem~\ref{pivot protocol is incentive compatible} shows that if the DA rule is incentive compatible, then the pivot protocol creates an incentive compatible mechanism.

Theorem~\ref{pivot protocol is incentive compatible} has presented the 
relationship between incentive compatibility of the DA rule and the resulting 
supply chain auction created by the Pivot Protocol. 
This brings up the question of whether the budget balance of the DA rule 
ensures budget balance of the supply chain mechanism. 
It turn out not to be so! 
In appendix~\ref{Appendix - McAfee's chain auction} we present an example of 
a DA rule (McAfee's rule) which has a revenue surplus, but the Pivot Protocol 
using that rule creates a mechanism with a revenue deficit. 

%In Section~\ref{Global properties of the different DA types} we examine several chain auctions created by different double auction rules, and list their properties.

% Actually, the total cost of one unit is never less than the price set to the suppliers in the consumer market, and never exceeded the sum of the bids of the first losing agent of each supplier markets:
% \begin{theorem} \label{pivot protocol payments}  If the double auction rule used in the pivot market is incentive compatible and non-discriminating, and $P_S$ is the seller's price in this auction, then the total payment $P$ to a supplier and converters which create one unit satisfies $P_S\le P \le S^t_{q+1} $, where $S^t_{q+1} $ is the sum of the bids of the first losing agent of the supply and conversion markets. \end{theorem}

The next theorem gives a condition on the DA rule which 
 is sufficient to ensure that the supply chain mechanism created by the 
Pivot Protocol is budget-balanced.
It also shows that a DA rule with budget deficit creates a mechanism with a 
deficit. 
\begin{theorem}
\label{pivot protocol BB} 
Let $R$ be a normalized DA rule that is IC and non-discriminating.
Let $M$ be the supply chain mechanism created by the Pivot 
Protocol using the rule $R$ .
For any supply and demand curves, let $q$ be the trade size decided by $R$, 
and let $P_S$ and $P_B$ be the sellers and buyers prices respectively.

If $P_B\ge S_{q+1}$ holds for all supply and demand curves,
then $M$ is budget-balanced.
If $P_B < P_S$ for some supply and demand curves ($R$ has budget deficit) 
then $M$ has budget deficit. 
\end{theorem}
\begin{proof}
We first show that if $P_B\ge S_{q+1}$ holds for all supply and demand curves,
then $M$ is budget-balanced.
We divide the supply chain allocation to $q$ disjoint procurement sets. 
Each set has a single winner from each market. We show that the total payment
from each procurement set is non-negative, therefore the auction is BB.
By Theorem~\ref{pivot protocol is incentive compatible} the mechanism is 
non-discriminating, so all procurement sets have the same payments.
Let $P$ be the total payments to all agents in a procurement set, except 
for the consumer. Lemma~\ref{pivot protocol payments} 
(see appendix~\ref{appendix - supply chain payments}) shows that 
$S^t_{q+1}\ge P\ge P_S$. 
If $P_B\ge S^t_{q+1}$ then $P_B\ge P$, and we conclude that $P_B-P\ge 0$ 
and $M$ is BB.

Similarly if for some supply and demand curves $R$ has budget deficit, 
then every procurement set has a deficit.
If $P_B < P_S$ for some supply and demand curves, 
then $P_B < P$ and we conclude that the total payment for each procurement
set is $P_B-P< 0$, which means that $M$ has a budget deficit.
\end{proof}

Note that for a double auction rule $R$ to be BB, it is sufficient that 
$P_B\ge P_S$. 
To prove that the supply chain mechanism is budget balanced, the theorem 
relies on a stronger condition that $P_B\ge S_{q+1}$ (it is always true that 
$S_{q+1}\ge P_S$ as Lemma~\ref{pivot protocol payments} shows).
While McAfee's DA satisfies $P_B\ge P_S$,  the stronger
condition $P_B\ge S_{q+1}$ does not always hold, and indeed the example in
Appendix~\ref{Appendix - McAfee's chain auction} shows that the supply chain
mechanism has a budget deficit in some cases. 
On the other hand, the Trade Reduction DA rule satisfies both
constraints since $q=l-1$ (recall that $l$ is the optimal trade size) and
$P_B = B_{q+1} = B_l  \ge S_l = S_{q+1} = P_S$.

%The next lemma present a bound on the total payment to the suppliers and the 
%converters in the pivot mechanism. This bound gives a condition on the
% double auction used by the pivot protocol which is sufficient to ensure that
%the supply chain mechanism is budget-balanced. 
%Theorem~\ref{pivot protocol and symmetric protocol equivalence} shows that for 
%some DA rules, this bound can be applied to the Symmetric Protocol as well.
%A single unit of the final good is created by one winning supplier and 
%one winning converter in each conversion market. 
%The total payment to all these agents is at 
%least the critical value of the ``sellers'' in the pivot market, but never 
%exceeds the minimal cost of creation of one more unit. 

%\begin{lemma}
%\label{pivot protocol payments} 
%If the double auction rule used in the Pivot Protocol is IR, IC and 
%non-discriminating, and $P_S$ is the ``seller's price'' in this double
% auction, then the total payment $P$ to a supplier and converters which 
%create one unit of the final good satisfies $P_S\le P \le S^t_{q+1} $.
%\end{lemma}
%\begin{proof}
%See appendix~\ref{appendix - supply chain payments}.
%% The proof of this theorem can be found in appendix~\ref{appendix - supply chain payments}.
%% if we remove the appendix then:
%% See \cite{BabaioffThesis}.
%\end{proof}

Clearly a DA rule that has budget deficit might create a supply chain
mechanism with budget deficit if used by the Symmetric Protocol. This is since
double auction is a special case of a supply chain.
We were not able to present a parallel sufficient condition for the Symmetric 
Protocol to ensure a budget-balanced supply chain mechanism. For a case that 
a normalized DA rule is incentive compatible, consistent and 
non-discriminating, the next theorem proves that the two protocols create the 
same mechanism, which implies that the above sufficient condition for budget
balance holds also for the Symmetric Protocol with such DA rules.

We now turn to look at the relationship between the two protocols.
In case that the normalized DA rule is consistent and non-discriminating it 
can be used 
by both protocols. The following theorem shows that if the rule is also IC,
 then the Symmetric Protocol and the Pivot Protocol create the same mechanism: 
\begin{theorem}
\label{pivot protocol and symmetric protocol equivalence} 
Let $R$ be a normalized DA rule that is non-discriminating and consistent.
If $R$ is IC then the mechanism created by the
 Pivot Protocol using $R$ is the same as the mechanism created by the
 Symmetric Protocol using $R$ (for any set of bids, 
both have the same allocation and payments).
Thus, the efficiency and the budget of both mechanisms are equal.
\end{theorem}

\begin{proof}
Since the supply and demand curves of the demand market $M^t$ are built in 
the same way, and the DA rule used by the demand market is the same in both 
protocols, the market trade sizes decided by the rule are the same in 
both mechanisms. The Symmetric Protocol is consistent, therefore the trade 
sizes in all the markets are the same. Since the mechanism is 
non-discriminating, the allocations are the same in all the markets in both 
protocols. 
By Observation~\ref{obs:single-payment} both mechanisms must have the same 
payments, since they have the same allocation.
%We now show that the payments are the same in both mechanisms. Since both mechanism are incentive compatible and have the same allocation, and the losing agents always pay zero, each agent pays his critical value in both mechanisms. The critical values of each agent must be the same in both mechanisms, since the allocation is the same. Assume in contradiction that an agent has two different critical values $c_1$ and $c_2$ in the two mechanisms, such that $c_1<c_2$. If he bids $T$ which satisfies $c_1<T<c_2$, then the agent wins in one mechanism and losses on the other, in contradiction to equivalence in the allocations of the two mechanisms.
%We conclude that the allocation and payments of the two mechanisms created by both protocols are the same, and therefore the mechanisms are the same.
\end{proof}


\subsection{Communication Complexity}
\label{Communication Complexity}
A naive implementation of a supply chain mechanism as a centralized mechanism 
would have required sending
$\Omega(t n)$ bids to one centralized point ($t$ is the number of goods and 
$n$ is the minimal number of agents in any market). 
Both protocols that we have 
described have much lower communication of $O(n)$ prices received and sent to 
each market (note that 
if a bid of a single agent requires $k$ bits, then the prices communicated 
do not grow too much and have at most $k+t$ bits). 
For many interesting DA rules we can further reduce the communication 
 of each market to only $O(log(n))$ prices by the improved Pivot Protocol we 
present below. 
Thus, for these DA rules the Pivot Protocol can be implemented for 
exponentially larger markets when still using the same bandwidth.
For example, we can use the improved protocol if the size of 
trade $q$ set by the DA rule can be calculated from the Optimal Trade Quantity 
$l$, and the payments are dependent on the $l$ and $l+1$ bids in the supply 
and demand curves only (this is the case for all DA rules we have presented). 

% Note that in all of the double auction rules that we have seen, the size of  trade $q$ is easily calculated from the Optimal Trade Quantity $l$ (it is either the same or one unit smaller). The payments are dependent on the $l$ and $l+1$ bids in the supply and demand curves only. 

% We can exploit this to reduce the communication complexity of the Pivot Protocol. We can reduce the communication on each link between consecutive markets from linear communication, to logarithmic communication. Thus, the pivot protocol can be use for exponentially larger markets when still using the same bandwidth.

\begin{theorem}
\label{pivot protocol communication complexity} 
Let $R$ be a normalized DA rule that is IC and non-discriminating.
Assume that the trade size decided by this rule is a function of the 
Optimal Trade Size $l$ only, and the payments can be decided using $O(1)$ 
prices when knowing $l$. Then the Pivot Protocol can be implemented with only 
$O(log(n))$ messages sent and received by each market, 
where each message contains a single price.
% If the double auction rule which is used in the pivot protocol is incentive compatible, non-discriminating and the trade size decided by this rule is a function of the Optimal Trade Size $l$ only, then the pivot protocol can be implemented with only $O(log(l))$ messages for each market, where each message contains $O(1)$ prices.
\end{theorem}

\begin{proof}
The Pivot Protocol can be improved by using binary search to find $l$ and 
thus sending only the few values needed from the supply curves, instead of 
passing entire supply curves along the chain. 
The search for $l$ can be preformed by a binary search while sending only 
$O(log(n))$ messages between any two consecutive markets. 
In the improved protocol, first $S^t_{n \over 2} $ is passed to the 
pivot market, for $n$ which is the minimal number of bids in any market (known 
to all markets by the protocol explained in the beginning of this section).
Then the pivot market checks if this value is smaller or greater than 
$D^t_{{n} \over 2} $ and asks for the ${{3\cdot {n}} \over 4}$ 
or the ${{n} \over 4}$ element of the supply curves respectively. 
The pivot market receives the requested value and continues in a similar way 
with the search, until $l$ is found. Then $O(1)$ prices needed from 
the supply curve to find the payments (which are only a function of $l$ by 
our assumption) are propagated to the pivot market by its request.
\end{proof}

% The Symmetric Protocol has no natural candidate to be the 
Similar results can be presented for the Symmetric Protocol with the same 
restrictions on the DA rule used by the protocol. 
The Symmetric Protocol is the protocol of choice when the DA rule is discriminating, but in this case
%But, this protocol should be used when the DA rule is discriminating and then 
it is more likely that entire supply and demand curves are needed in order 
to find the prices for all winners.

% The idea is to use binary search to find $l$ and thus send only the few values needed from the supply curves, instead of passing the entire supply curves along the chain.
% , thus reducing the communication between the markets. The binary search for $l$ can be preformed by sending only $O(log(l))$ messages, where each message contain $O(1)$ prices, between any two consecutive markets.
% So, as we have seen, even though the symmetric protocol is more natural in a sense, it has a problem that it cannot be used with inconsistent rules. The pivot protocol does not have this limitation and is more efficient when looking on the communication volume.

% ---------------------------------------------------------------------------

\subsection{Global Properties of the Different DA Types}
\label{Global properties of the different DA types}
% MOSHE : Suggestion \section{Global properties of the different Supply Chain Auction types}

In this section we examine the properties of the mechanisms created by the 
supply chain protocols using different double auction rules.

% ---------------  Chain of VCG

{\bf Chain of VCG Double Auctions} is created by running the Symmetric 
Protocol using the VCG DA rule. This creates a local VCG double auction in 
each of the markets. 
% In Theorem~\ref{The Chain of VCG auctions is VCG} we show that the auction is a VCG auction in the broad sense - it is efficient and in this auction each agent pays the damage his bid caused to all the other traders, as in a general VCG auction. 
Since VCG DA rule is IR, IC, consistent and non-discriminating, by Theorem~\ref{pivot protocol and symmetric protocol equivalence} the Pivot Protocol with the VCG DA rule creates the same mechanism.

%\begin{theorem}
%\label{The Chain of VCG auctions is VCG} 
%The Chain of VCG auctions satisfy the definition of a VCG mechanism.
%\end{theorem}
%\begin{proof}
%The outcome maximizes the sum of valuations, since the trade size is the Optimal Trade Size and the best bidders in each of the markets are chosen as winners. We should show that the payments functions are by the VCG scheme. Lets look for example at a winning convert $S^{r\to r+1}_j$. This agent receives $min(S^{r\to r+1}_{l+1},D^{r\to r+1}_l)$ and this is exactly the increment in the social efficiency cause by his bid, since if $S^{r\to r+1}_{l+1} \le D^{r\to r+1}_l$, withdrawing his bid will not cause any change in the trade size, which means that  $S^{r\to r+1}_j$ caused agent $S^{r\to r+1}_{l+1}$ to lose the auction and thus $S^{r\to r+1}_{l+1}$ is the damage prevented by his bid. On the other hand, if  $S^{r\to r+1}_{l+1} > D^{r\to r+1}_l$ withdrawing his bid will cause the trade size to be one unit smaller, which means that agents that submitted the $l$ bid in each market would not have won. In this case the damage prevented is the sum of valuations of these agents, which is exactly
%$
%D^t_l - (\sum_{m=1}^{r-1} S^{m\to m+1}_l + \sum_{m=r+1}^{t-1} S^{m\to m+1}_l + S^1_l) = 
%(D^t_l - \sum_{m=r+1}^{t-1} S^{m\to m+1}_l) - (S^1_l+\sum_{m=1}^{r-1} S^{m\to m+1}_l) =
%D^{r+1}_l - S^{r}_l  = 
%D^{r\to r+1}_l 
%$.
%Similar arguments can be use to prove that all other agents pay the damage they caused.
%  \end{proof}

The following proposition summarizes the properties of the supply chain mechanism using the VCG double auction rule. 
\begin{proposition} 
\label{Chain of VCG Double Auctions theorem} 
Chain of VCG Double Auctions is IR, IC, non-discriminating, 
Socially Efficient and has a revenue deficit. ($R_{Chain\ VCG}\le 0$)
\end{proposition}
\begin{proof}
Since VCG DA rule is normalized, IC and non-discriminating, by 
Theorem~\ref{pivot protocol is incentive compatible} the mechanism created
is IR, IC and non-discriminating.
The outcome maximizes the sum of valuations (Socially Efficient), 
since agents bid truthfully, the trade size is the Optimal Trade Size and 
the highest value bidders in each of the markets are chosen as winners.
% The mechanism is incentive compatible and socially efficient because it is a VCG mechanism by Theorem~\ref{The Chain of VCG auctions is VCG}, and any VCG mechanism is socially efficient and incentive compatible. %  by Theorem~\ref{grovesthm}.

By the fact that VCG DA has budget deficit and Theorem~\ref{pivot protocol BB}
we conclude that the Chain of VCG DAs has budget deficit.
% The revenue is non-positive since by Lemma~\ref{pivot protocol payments} the total payment for a supplier and converters of one unit $P$ satisfies $P_S\le P$, where $P_S$ is the payment to the seller in the pivot market. In a VCG rule it is always true that $P_B\le P_S$, where $P_B$ is the payment from the buyer in the pivot market, therefore $P_B\le P$. We conclude that the cost $P$ of a unit is never less than the payment $P_B$ received from the buyer of that unit, and therefore there is always a budget deficit.
\end{proof}

Note that by Observation~\ref{obs:single-payment} the mechanism created 
using VCG DA rule is VCG in the global sense presented by Vickrey, Clarke and 
Groves (A mechanism that is IR, IC and efficient). 

%  and we summarize the results in the following theorem.
% Figure~\ref{Supply Chain Auctions} summarizes the properties of the mechanisms created by the protocols using different double auction rules.
% ---------------  Chain of Trade Reduction

{\bf Chain of Trade Reduction Double Auctions} is created by running the Symmetric Protocol using the Trade Reduction DA Rule. This creates a local Trade Reduction double auction in each of the markets, and those double auctions are chained. 
Since the Trade Reduction DA rule is normalized, IC, consistent and 
non-discriminating, 
by Theorem~\ref{pivot protocol and symmetric protocol equivalence} 
the Pivot Protocol with the Trade Reduction DA rule creates the same mechanism.

\begin{proposition}
\label{Chain of Trade Reduction Double Auctions theorem}
Chain of Trade Reduction Double Auctions is IR, IC , non-discriminating, 
has a revenue surplus of 
$$
R_{Chain\ Trade\ Reduction} = (l-1)\cdot (D^t_l-S^t_l)\ge 0
$$
the reduction in the Social Efficiency is $D^t_l-S^t_l$
and its efficiency is at least $(l-1)/l$ of the maximal efficiency.
\end{proposition}

\begin{proof}
Since the Trade Reduction DA rule is normalized, IC and ND, by 
Theorem~\ref{pivot protocol is incentive compatible} the mechanism created
is IR, IC and non-discriminating.

% The Chain of Trade Reduction Double Auction is created by the symmetric protocol using the Trade Reduction DA rule which is incentive compatible, non-discriminating and consistent, thus by Theorem~\ref{symmetric protocol is incentive compatible} the mechanism is incentive compatible, and non-discriminating. 

The revenue is the sum of the payments which is 
$$(l-1)\cdot (D^t_l- \sum_{r=1}^{t-1} S^{r\to r+1}_l-S^1_l) = 
 (l-1)\cdot (D^t_l-S^t_l)$$
 and it is non-negative since $D^t_l\ge S^t_l$ by the definition of The Optimal Trade Quantity $l$.

The reduction in social efficiency is $D^t_l-S^t_l$, since the $l$ unit is not traded, so
as in the Trade Reduction DA the $l-1$ highest trades out of the optimal $l$ trades are conducted, giving 
efficiency of at least $(l-1)/l$. 
\end{proof}

% ---------------  Chain of $\alpha$ Reduction
{\bf Chain of $\alpha$ Reduction Double Auctions} is created by running the Pivot Protocol using the $\alpha$ Reduction Rule, which creates a randomized mechanism. This mechanism is a probability distribution over two mechanisms - the Chain of Trade Reduction DA and the Chain of VCG DA. The mechanisms are used according to a random variable $\chi$ that is one with probability $\alpha$ and zero otherwise. The first mechanism is chosen if $\chi$ is one (with probability $\alpha$), and the second mechanism is chosen if $\chi$ is zero (which happens with probability $1-\alpha$).
 
This auction can also be preformed using the Symmetric Protocol under the 
public coin assumption (which can be created by distributing a random coin, 
tossed by one of the markets).
In this case the random variable $\chi $ is shared by all the markets, meaning that either the Trade Reduction rule is used by all the markets, or by non of the markets. This ensures trade consistency and creates the same mechanism.

%\begin{definition}
Chain of $\alpha$ Reduction Double Auctions achieves the allocation and payments of the Chain of Trade Reduction DA with probability $\alpha$, and with probability $1-\alpha$ it achieves the allocation and payments of the Chain of VCG DA.

\begin{proposition}
\label{chain of alpha reduction DA properties}
Chain of $\alpha$ Reduction Double Auctions is an individually rational and  
universally incentive compatible randomized mechanism. Its expected revenue is 
$$ 
R_{Chain\ \alpha\ Reduction} = \alpha \cdot R_{Chain\ Trade\ Reduction} + (1-\alpha ) \cdot R_{Chain\ VCG}  
$$ 
its efficiency is at least $(l-1)/l$ of the maximal efficiency.
Its expected reduction in the Social Efficiency is $\alpha \cdot(D^t_l-S^t_l)$ when the expectation is over the random choice of $\chi$.

\end{proposition}
\begin{proof}
The mechanism is individually rational and universally incentive compatible randomized mechanism, since both the Chain of Trade Reduction DAs and the Chain of VCG DAs are normalized and incentive compatible by Proposition~\ref{Chain of Trade Reduction Double Auctions theorem} and Proposition~\ref{Chain of VCG Double Auctions theorem}.

It is easy to verify that the expected revenue and the reduction in social efficiency are as claimed.
\end{proof}

% ---------------------------------------------------------------------------
% ---------------  Chain of $\alpha$ Payment
{\bf Chain of $\alpha$ Payment Double Auctions} is created by running the Symmetric Protocol, and in each market running the $\alpha$ Payment Double Auction, which creates a randomized mechanism (again under the public coin assumption). 
% This mechanism is a probability distribution over two mechanisms that are not incentive compatible, but this mechanism is incentive compatible. 
The mechanism has the same expected revenue and social efficiency as The Chain of $\alpha$ Reduction DAs, and each of the agents has the same probability of winning the auction and the same expected utility as in The Chain of $\alpha$ Reduction DAs.
Note that since the $\alpha$ Payment DA rule is discriminating, the Pivot 
Protocol as defined above cannot be used to create a supply chain mechanism.

\begin{proposition}
\label{chain of alpha payment DA properties}
Chain of $\alpha$ Payment Double Auctions is an individually rational and 
incentive compatible randomized mechanism. Its expected revenue and its expected social efficiency is the same as The Chain of $\alpha$ Reduction Double Auctions.
\end{proposition}
 
\begin{proof}
The Chain of $\alpha$ Payment Double Auctions has the same distribution of the allocation and payments as The Chain of $\alpha$ Reduction Double Auctions,  therefore each agent is facing the same mechanism in expectation so he bids truthfully. Since the expected payment to each agent is the same in both mechanisms, the expected revenue is the same. Since the allocation is the same in both mechanisms, the expected social efficiency is the same.
\end{proof}

% --------------- Chain of McAfee
Unfortunately, chaining McAfee's Double Auction does not preserve the nice properties McAfee's DA rule has. If we run the Symmetric Protocol using McAfee's DA Rule, we might get an inconsistent trade. On the other hand, if we run the Pivot Protocol using McAfee's DA rule, we have a revenue deficit! (See examples in appendix~\ref{Appendix - McAfee's chain auction}). 
 However a weaker claim can be made - this mechanism has revenue at least as high as the chain of VCG DA, and has efficiency at least as high as the chain of Trade Reduction DA.

{\bf Chain of McAfee's Double Auction} is created by running the Pivot Protocol using McAfee's Rule.

\begin{proposition}
\label{chain of mcafee DA properties}
Chain of McAfee's Double Auction is IR, IC, ND, its revenue is never smaller than the revenue of the Chain of VCG Double Auction, and its reduction in the Social Efficiency is never greater than the reduction of the Chain of Trade Reduction Double Auction.
\end{proposition}

\begin{proof}
Chain of McAfee's Double Auction is IR, IC and ND by 
Theorem~\ref{pivot protocol is incentive compatible} and the fact that 
McAfee's DA rule is normalized, IC and ND.

The mechanism revenue is never smaller than the revenue of the Chain of VCG 
Double Auctions since if there is trade reduction, then there is a revenue 
surplus by Proposition~\ref{Chain of Trade Reduction Double Auctions theorem}, 
and we know that Chain of VCG Double Auctions has a revenue deficit by 
Proposition~\ref{Chain of VCG Double Auctions theorem}. In the case of no trade 
reduction, the revenue is never smaller than the revenue of the Chain of VCG 
Double Auctions, since each winning buyer pays 
$p = P_B = P_S = {S^t_{l+1}+D^t_{l+1} \over 2}$ which is at least 
as much as he pays in the VCG mechanism.
This is because $S^t_{l+1} > D^t_{l+1}$ so $S^t_{l+1} > p > D^t_{l+1}$ 
and $S^t_l\le p$ 
and therefore $max(D^t_{l+1}, S^t_l) \le p$. Each winning seller of the supply 
good, never receives more than $min( S^1_{l+1},D^1_l)$ which he receives in the VCG mechanism. This is since 
% $p < S^t_{l+1}$ and $p\le D^t_l$, and therefore 
$p\le min(S^t_{l+1},D^t_l)$ and he receives 
$$
min(S^1_{l+1},p-\sum_{r=1}^{t-1}\gconv{S}{r}_{l}) \le
min(S^1_{l+1},min(D^t_l,S^t_{l+1})-\sum_{r=1}^{t-1}\gconv{S}{r}_{l})  =$$
$$
min(S^1_{l+1}, D^t_l-\sum_{r=1}^{t-1}\gconv{S}{r}_{l} ,S^t_{l+1}-\sum_{r=1}^{t-1}\gconv{S}{r}_{l}) =
min ( S^1_{l+1},D^1_l) 
$$
Where the last equality holds since 
$D^1_l = D^t_l-\sum_{r=1}^{t-1}\gconv{S}{r}_{l}$ and 
$S^t_{l+1}-\sum_{r=1}^{t-1}\gconv{S}{r}_{l} \ge S^t_{l+1}-\sum_{r=1}^{t-1}\gconv{S}{r}_{l+1} = S^1_{l+1}$.
A similar argument shows that each winning convert never receives more than in the VCG mechanism.
  
The reduction in the social efficiency is never greater than the reduction in the Chain of Trade Reduction Double Auction, since the trade size is never smaller than the trade size in this auction, which is the $l-1$.
% Optimal Trade Size minus one.
\end{proof}

% ----------------------------------------------------------
Table~\ref{Supply Chain Auctions} summarizes the properties of the 
supply chain mechanisms created by the two protocols using different double 
auction rules. 
For normalized mechanisms, if one cares about incentive compatibility and 
efficiency but not about budget balance, then the VCG mechanism should be used.
If budget balance must be ensured for {\bf every} execution of an incentive
compatible mechanism, 
then the Trade Reduction auction is the mechanism of choice.
If one wants the mechanism to be incentive compatible for every execution,
but can settle for expected budget balance instead of ensured one, then higher
expected efficiency can be achieved by the $\alpha^\ast(D)\ Reduction$, 
assuming the right choice of $\alpha^\ast(D)$. Finally, if the variance in the
agents payments is important, then the $\alpha^\ast(D)\ Payment$ should be 
used in order to lower the variance for most agents. This has a cost, since 
now the mechanism is not incentive compatible for every execution 
(universally), but rather, it is incentive compatible when the agents only 
care about expected utility. 
The table also presents the McAfee supply chain mechanism, to point out the 
fact that the budget of the supply chain mechanism might be different from 
the budget of the underlying double auction. 


%\begin{theorem}
%\label{chain auction properties}
%The properties of chains of auction are as appear in Figure~\ref{Supply Chain Auctions}.
%\end{theorem}

%\begin{proof}
%See theorems~\ref{Chain of VCG Double Auctions theorem}, 
%~\ref{Chain of Trade Reduction Double Auctions theorem},
%~\ref{chain of alpha reduction DA properties},
%~\ref{chain of alpha payment DA properties},
%~\ref{chain of mcafee DA properties}
%and \cite{BabaioffThesis}.
%\end{proof}

\input{chain_auctions.tex}

When comparing the properties of the chain mechanisms in 
Table~\ref{Supply Chain Auctions} with the properties of the original double 
auction rules in Figure~\ref{Double Auction Rules}, one can see the following.
 The incentive compatibility and the efficiency properties are preserved 
by the protocols, while achieving a revenue surplus requires a stronger 
condition on the DA rule, as we have shown in Theorem~\ref{pivot protocol BB}.
% can be seen in appendix~\ref{Appendix - McAfee's chain auction}. 
The consistency property, which enables chaining of the markets by the Symmetric Protocol, applies to the first two deterministic rules, and the two randomized rules under the assumption of common coin toss. It does not exist in McAfee's rule since this rule sets its trade quantity as a function of the bids submitted, in such a way that the trade quantity can be different in two different markets. The k-DA is not presented in the table since it is not incentive compatible and therefore it cannot be used by the protocols (the two protocols create different mechanisms with this rule).

% Note that the supply chain auction created by the VCG rule, is a VCG auction in the broad sense - each of the agents pays the damage his bid caused to the other agents.

% ---------------------------------------------------------------------------

%\section{Extensions}
%\label{Extensions}
%\subsection{Multi-Unit Bids}
%\label{Multi-Unit Bids}
%A simple extension to the model we have seen above is a model in which 
%an agent can place multiple equal bids in the same market instead of only one 
%bid. 
%For example, a selling bid in this case can be of the form $(q,p)$ which means 
%that this agent is willing to sell up to $q$ units for at least $p$ per unit. 
%Some of the double auction rules presented in this paper can be extended to 
%support this model as well.  

%Specifically, in order for the Trade Reduction rule to retain its IR, IC and 
%revenue surplus properties, it is sufficient that the reduction from the 
%optimal trade size $l$ is of size $Q$, 
%where $Q$ is the a-prior maximal amount that can be requested by any agent. 
%The payment of an agent winning $\hat{q}\le q$ units is the sum of the 
%highest $\hat{q}$ losing bids not submitted by him in its market.
% This auction is still IR and IC, and the efficiency is at least $(l-Q)/l$. 
 
%The Symmetric Protocol can use these extended double auction rules to create a 
%supply chain auction. 
%To extend the Pivot Protocol, $Q$ values must be sent backwards in the supply 
%chain, instead of only one value. For more details see~\cite{BabaioffThesis}.

%\subsection{Trees of Auctions}
%Clearly a linear topology supply chain is only a simple form of a supply chain, which in general may take the form of an arbitrary directed a-cyclic graph. Our Pivot Protocol is easily extended to the case of trees. In the linear topology supply chain that we have seen so far, a good is created by conversion from one specific good. In the tree extension, each good can be created from one of several goods. For example, we might have a lemon market in Florida and another lemon market in California, and also separate squeezing markets in both states, but only one lemonade market. The tree of auctions decides how many lemonade glasses will be produced, and how many of the glasses will be produced from Florida lemons and from California lemons. 
%For more details about the extension of the Pivot Protocol to this case see ~\cite{BabaioffThesis}. 
%% We do not know how to extend our results to the general case of DAGs.

%% Moshe  - Say that we do not handle complementary which is a BIG problem.
% ---------------------------------------------------------------------------
\section{Discussion and Future Work}
\label{sec:Future}
In this paper we have presented two distributed protocols that create supply 
chain mechanisms using double auction rules. 
Our protocols are generic and can use different double auction rules to create
 different mechanisms. We have characterized the properties of the supply
chain mechanisms which derive from the properties of the underlining double 
auction rule. 
The protocols can use the VCG DA to achieve IR, IC and full efficiency
with budget deficit. They can also use the Trade Reduction DA to ensure budget
 balance or surplus with high efficiency. 
An even higher efficiency  while maintaining BB in expectation can be achieved 
% We have shown how to create an IR, IC, ex ante budget-balanced yet highly efficient mechanisms
using our two new randomized double auction rules. 

Our work concentrated on the simple case of indivisible homogeneous goods, 
where each of the agents desires only one good or desires to convert one unit 
of good to one unit of another good, and the supply chain has a linear form.
Our Pivot Protocol is easily extended to the case of trees in which 
 each good can be created from one of several goods (but no good is used to
 create two different goods). For example, we might have a lemon market in 
Florida and another lemon market in California, and also separate squeezing 
markets in both states, but only one lemonade market. The tree of auctions 
decides how many lemonade glasses will be produced, and how many of the 
glasses will be produced from Florida lemons and from California lemons. 
Since the main ideas in this extension are similar to the ones presented in 
this paper, we omit the technical details and refer the interested reader 
to Babaioff~\citeyear{BabaioffThesis} for the details. 
Babaioff~\citeyear{BabaioffThesis} also discusses an extension of the model 
to the case that an agent is allowed to bid for multiple units in its market,
by bidding the maximal quantity it is willing to trade and the price per unit.

A paper by~\citeA{babaioffWalsh03} extends our model 
to the case that each item is produced from a combination of several items 
of several different goods, but each good is still produced in exactly one 
market. 
They have presented a specific auction (unlike this
work which presents generic protocols for supply chain formation) that is 
individually rational, incentive compatible, budget-balanced, yet 
highly efficient. 

Similar results (IR, IC, BB and high efficiency) have been presented 
by~\citeA{BNP04} to a related model of 
% by Babaioff, Nisan and Pavlov~\citeyear{BNP04} to a related model of 
Spatially Distributed Market. In this model a single good is traded in a 
set of independent markets, where shipment between markets is possible but 
incurs a publicly known cost (but in their model there are no strategic 
producers as in our model).

One interesting challenge is to stay with the unit-to-unit conversion model, 
but extend our model to allow a general directed a-cyclic supply chain 
graph topology.
Yet another important challenge is to extend the model to a case where 
agents are not single-minded agents, and can submit exclusive or non 
exclusive bids in several markets.
% , and those bids are expressed at different bidding languages (for example by placing OR and XOR bids). 

% Old:
%Our work concentrated on the simple case of indivisible homogeneous goods, 
%where each of the agents desires only one good or desires to convert one unit 
%of good to one unit of another good. 
%% We relay on multiple agents in each market to achieve efficiency.
%We have assumed that the supply chain has a linear or tree form. 
%One interesting challenge is to stay with the unit-to-unit conversion model, 
%but extend our model to a general directed a-cyclic graph topology.
%% , where one item of a good can be created from good .
%Another interesting challenge is to achieve similar results when one 
%removes the restriction of one to one 
%conversion and looks at a model where each item is produced from a 
%combination of several items of several different goods.
%Yet another important extension of the model is the case where each agent can 
%submit bids in several markets, and those bids are expressed at different bidding languages (for example by placing OR and XOR bids). 
 

%%%%%%%%%%%%%%%ACK

%\smallspace
%\noindent
%{\bf Acknowledgments:} We thank William Walsh, Daniel Lehmann, 
%Hila Wallerstein and the anonymous reviewers for their helpful comments.
\pagebreak
\acks{
This research was supported by grants from the Israeli Ministry of Science, the Israeli Academy of Sciences and the USA-Israel Bi-national Science Foundation. The first author (Babaioff) was also supported by Yeshaya Horowitz Association.

We thank William Walsh, Daniel Lehmann, 
Hila Babaioff and the anonymous reviewers for their helpful comments.}

% \pagebreak
%% \bibliographystyle{alpha}
%\bibliographystyle{plain}
%\bibliography{bib}
%% \input{psfig}

%%%\pagebreak

% ---------------------------------------------------------------------------- 
\appendix
\cout{ % remove this appendix - it was added to the text.
\section{DA rules}
\label{appendix - DA rules}
In this appendix we survey some double auction (DA) rules. In all the rules, supply and demand graphs are created by sorting the bids in non-descending and non-ascending order respectively. Then the trade quantity and the payments to the agents are determined. 

We denote by $S_i$ the $i$-th supply bid (in the sorted order), and by $B_j$ the $j$-th demand bid (in the sorted order). 
We denote by $l$ {\em the optimal trade quantity}, $l$ is maximal such that $B_l\ge S_l$. Trading $l$ units maximizes the efficiency if the agents bids are the agents true values. 
In all the following double auctions, non-trading agents pay zero, and once the trade quantity $q$ is set, the trading agents are the first $q$ sellers and $q$ buyers. We call a double auction rule {\em non-discriminating} if the price paid by all trading buyers is the same, and the price paid to all trading sellers is the same (but we do not require that the buyers price will be the same as the sellers price as in a uniform priced auction). 

It is known that a double auction mechanism cannot be efficient, incentive compatible and budget balanced, under the condition that non trading agents pay zero. The VCG double auction is efficient and incentive compatible, but is not budget balanced. The k-DA (presented below) is an efficient double auction with zero revenue but is not budget balanced. McAfee~\cite{mcafee92dominant} suggested an incentive compatible and budget balanced DA, with some reduction in efficiency in some cases. We suggest extending this concept of trading efficiency with revenue, and to use randomization in the allocation and payments rules in order to achieved high efficiency with expected revenue of zero.

We present the different double auction types and their properties:
\begin{itemize}

\item The VCG DA - $l$ units of the good are traded, each trading buyer pays $max(S_l, B_{l+1})$, and each trading seller receives $min(S_{l+1},B_l)$.

\item The k-DA~\cite{wilson85incentive,chatterjee83bargaining}- Before the auction begins, a parameter $k$ is chosen such that $k\in \lbrack 0,1 \rbrack $. $k$ is used to calculate a clearing price $P=k\cdot S_l + (1-k)\cdot B_l$. $l$ units of the good are traded at the price of $P$.

\item The Trade Reduction DA - $l-1$ units of the good are traded, each trading buyer pays $B_l$, and each trading seller receives $S_l$. (this is a simple version of McAfee's DA)

\item McAfee's DA \cite{mcafee92dominant}- if a suggested clearing price $p = {S_{l+1}+B_{l+1} \over 2}$ is accepted by the $l$ buyer and seller (${p\in \lbrack S_l,B_l\rbrack}$) then $l$ units of the good are traded at the price of $p$, otherwise the Trade Reduction rule is used.  

% Moshe: Do we want to say something about McAfee's DA ? maybe to give cite to appendix?:
% \item McAfee's DA - We suggest so generalization of McAfee's DA, details can be found in appendix XXXXX 

\end{itemize}

We suggest two new randomized double auction rules, which capture the tradeoff between the auction efficiency and the budget balance with one parameter $\alpha$:
\begin{itemize}

\item The $\alpha$ Reduction DA - Before the auction begins, a parameter $\alpha$ is chosen such that $\alpha\in \lbrack 0,1 \rbrack $. Then the bids are submitted. With probability $\alpha$ the Trade Reduction DA rule is used, and with probability $1-\alpha$ the VCG DA rule is used.

\item The $\alpha$ Payment DA - A parameter $\alpha$ is chosen as in the $\alpha$ Reduction DA. Then the bids are submitted and the allocation and payments are decided. $l-1$ units are traded between buyers which pay $\alpha\cdot B_l+(1-\alpha )\cdot max(B_{l+1}, S_{l})$ and sellers which receive $\alpha\cdot S_l+(1-\alpha )\cdot min(S_{l+1}, B_{l})$. With probability $\alpha$ another unit of the good is traded between a buyer which pays $max(B_{l+1}, S_{l})$ and a seller which receives $min(S_{l+1}, B_{l})$. (Note that the trade size and the allocation have the same distribution as in the $\alpha$ Reduction DA and each trading agent pays his expected payment in the $\alpha$ Reduction DA.)

% Moshe: Do we want to say something about McAfee's DA ? maybe to give cite to appendix?

\end{itemize}
In both of these auction, as $\alpha$ grows from zero to one, the probability of trade reduction increases, and as a result the expected revenue increases and the expected efficiency decreases. The VCG auction has a revenue deficit and the Trade Reduction auction has a revenue surplus, so if the distribution of the agents values is known prior to the beginning of the auction, the parameter $\alpha$ can be chosen such that the expected revenue is zero. We denote this value of $\alpha$ as $\alpha^\ast$.

} % cout
\section{Problems with Chaining McAfee's Double Auction}
\label{Appendix - McAfee's chain auction}

{\bf The Consistency Problem}: The following example of supply chain auction using McAfee's rule shows that 
not all double auction rules are consistent. Figure~\ref{example table2} shows
 the supply and demand curves in the three markets after the supply and demand
 curves propagation.
\input{table2.tex}

The optimal trade quantity in this example is $1$, as can be seen in Figure~\ref{example table2}. McAfee's rule in the Lemonade Market set the trade size to $1$, since ${{27+17}\over 2}=22\in {\lbrack 15, 25 \rbrack}$. On the other hand, if we use McAfee's rule on the Squeezing Market, trade reduction should be made since ${{7+(-3)}\over 2}=2\notin {\lbrack 5, 15 \rbrack}$ and the trade quantity is zero, in contradiction to the previous decision. We conclude that there 
exists a non-consistent DA rule that cannot be used by the Symmetric Protocol.

{\bf The Revenue Problem}: The same example with the Pivot Protocol presented in 
Figure~\ref{example table3} shows that the fact that the DA rule has revenue 
surplus, does not ensure that the supply chain mechanism created by the 
Pivot Protocol using the DA rule has a revenue surplus as well.

\input{table3.tex}

In this example, McAfee's rule in the Lemonade Market sets the trade size to $1$, since ${{27+17}\over 2}=22\in {\lbrack 15, 25 \rbrack}$. The buyer in this market should pay 22. By following the Pivot Protocol, the squeezer that has a bid of 5 should be paid $7=min(7, 22-10)$ and the supplier in the supply market that has a bid of 10 should be paid $17=min(17 , 20)$. The total revenue is $22-7-17 = -2$ which means that there is a revenue deficit.

\section{Supply Chain Payments}
\label{appendix - supply chain payments}
In this appendix we prove Lemma~\ref{pivot protocol payments} which is used in the proof of Theorem~\ref{pivot protocol BB}.
\begin{lemma}
\label{pivot protocol payments} 
If the double auction rule used by the Pivot Protocol is IR, IC and 
non-discriminating, and $P_S$ is the ``seller's price'' in this double
 auction, then the total payment $P$ to a supplier and converters 
(one from each market) which 
create one unit of the final good satisfies $P_S\le P \le S^t_{q+1} $.
% If the double auction rule used in the pivot market (the demand market) creates an incentive compatible non-discriminating double auction, and $P_S$ is the ``seller's price'' in this auction, then the total payment $P$ to a supplier and converters which create one unit satisfies $P_S\le P \le S^t_{q+1} $.
\end{lemma}
\begin{proof}

% We know that $S^t_{q}\le P_S \le S^t_{q+1} $ because $P_S$ is the critical 
% value in the non-discriminating double auction of the pivot market. 
% Below we prove that $P_S\le P \le S^t_{q+1} $.

By induction, each conversion market of $C^m$ to $C^{m+1}$ receives the pair $(P_S - \sum_{r=m+1}^{t-1} \cconv{q}{r}, q)$ from its demand market, and the payment to a winning converter is 
$$ min( P_S - \sum_{r=m+1}^{t-1} \cconv{q}{r} - S^m_q, \cconv{q+1}{m}) $$

Similarly, the supply market $M^1$ receives the pair $( P_S - \sum_{r=1}^{t-1} \cconv{q}{r}, q)$, and the payment to a winning supplier is 
$$ min(P_S - \sum_{r=1}^{t-1} \cconv{q}{r}, S^1_{q+1}) $$
We conclude that the total payment to the converters and supplier of one unit is 
$$ P =
\sum_{m=1}^{t-1}
	min( P_S - \sum_{r=m+1}^{t-1} \cconv{q}{r} - S^m_q, \cconv{q+1}{m}) +
min( P_S - \sum_{r=1}^{t-1} \cconv{q}{r}, S^1_{q+1})  
$$
First notice that $P \le S^t_{q+1} $ since 
$$
P\le \sum_{m=1}^{t-1}\cconv{q+1}{m} + S^1_{q+1}  = S^t_{q+1} 
$$
Secondly we should prove that $P_S\le P $. The idea of the proof is that this holds if there was only one conversion from $C^1$ to $C^t$ (as we show in Lemma~\ref{payment lemma1}), and by splitting a conversion to two consecutive conversions, the total payment to all the converters only grows (as we show in Lemma~\ref{payment lemma2}).  

\begin{lemma}
\label{payment lemma1}
Assume that there was only one conversion market from $C^1$ to $C^t$, which means that for every $i$, $S^{1\to t}_i = \sum_{r=1}^{t-1}\cconv{i}{r} $
then 
$$
P_S\le P = min(P_S - S^1_q, S^{1\to t}_{q+1}) + 
	   min(P_S - S^{1\to t}_q, S^1_{q+1})
$$
\end{lemma}
\begin{proof}
Note that the double auction in the pivot market is the same as in the original auction, since the supply curve of the pivot market is the same, and therefore $P_S$ is the same.

We prove that this claim is true by checking the four possible cases:
\begin{enumerate}
\item if $P_S - S^1_q\le S^{1\to t}_{q+1} $ and $P_S - S^{1\to t}_q\le S^1_{q+1}$, then 
$$P = (P_S - S^1_q) + (P_S - S^{1\to t}_q) = P_S + (P_S - (S^1_q + S^{1\to t}_q))\ge P_S $$
since $P_S \ge S^1_q + S^{1\to t}_q = S^t_q$, because the DA rule is non-discriminating.

\item if $P_S - S^1_q\le S^{1\to t}_{q+1} $ and $S^1_{q+1}\le P_S - S^{1\to t}_q$, then 
$$P = (P_S - S^1_q) + S^1_{q+1} = P_S + (S^1_{q+1}- S^1_q)\ge P_S $$
since $S^1_{q+1}\ge S^1_q$

\item if $S^{1\to t}_{q+1} \le P_S - S^1_q$ and $P_S - S^{1\to t}_q\le S^1_{q+1}$, then 
$$P = S^{1\to t}_{q+1} + (P_S - S^{1\to t}_q) = P_S + (S^{1\to t}_{q+1} - S^{1\to t}_q)\ge P_S $$
since $S^{1\to t}_{q+1} \ge S^{1\to t}_q$.

\item if $S^{1\to t}_{q+1} \le P_S - S^1_q$ and $ S^1_{q+1} \le P_S - S^{1\to t}_q$, then 
$$P = S^{1\to t}_{q+1} + S^1_{q+1} \ge P_S $$
since $S^{1\to t}_{q+1} + S^1_{q+1} =  S^t_{q+1}\ge P_S $, because the DA rule is non-discriminating.
\end{enumerate}
So we have proven that $P\ge P_S$ in the case of one conversion market.
\end{proof}

\begin{lemma}
\label{payment lemma2}
Assume that a conversion market from $C^k$ to $C^t$ is split into two conversion markets - one from $C^k$ to $C^{k+1}$ and the other from $C^{k+1}$ to $C^t$,
then the payment for conversion of one unit from $C^k$ to $C^t$ can only grow, which means that
$$  P^{k\to t} \le P^{k\to k+1} + P^{k+1\to t} $$
where $ P^{w\to z} $ is the cost of conversion of one $w$ unit to one $z$ unit. In other words, it is always true that
$$ 
min(P_S - S^k_q, S^{k\to t}_{q+1}) \le 
	min(P_S - S^{k+1\to t}_{q} - S^k_q, S^{k\to k+1}_{q+1}) +
	min(P_S - S^{k+1}_q, S^{k+1\to t}_{q+1}) 
$$
where $S^{k\to t}_i = \sum_{r=k}^{t-1}\cconv{i}{r} $
\end{lemma}
\begin{proof}
Note that the double auction in the pivot market is the same as in the original auction, since the supply curve of the pivot market is the same, and therefore $P_S$ is the same.

We prove that this claim is true by checking the four possible cases:
\begin{enumerate}
\item if $P_S - S^{k+1\to t}_{q} - S^k_q\ge S^{k\to k+1}_{q+1} $ and $P_S - S^{k+1}_q\ge S^{k+1\to t}_{q+1}$, then 
$$P^{k\to k+1} + P^{k+1\to t} = S^{k\to k+1}_{q+1}+S^{k+1\to t}_{q+1} = S^{k\to t}_{q+1} \ge min(P_S - S^k_q, S^{k\to t}_{q+1}) = P^{k\to t} 
$$

\item if $P_S - S^{k+1\to t}_{q} - S^k_q\le S^{k\to k+1}_{q+1} $ and $P_S - S^{k+1}_q\ge S^{k+1\to t}_{q+1}$, then 
$$
P^{k\to k+1} + P^{k+1\to t} = (P_S - S^{k+1\to t}_{q} - S^k_q) + S^{k+1\to t}_{q+1} =
$$
$$ (P_S - S^k_q) +  ( S^{k+1\to t}_{q+1}- S^{k+1\to t}_{q}) \ge P_S - S^k_q \ge P^{k\to t} 
$$ 
since $ S^{k+1\to t}_{q+1}\ge S^{k+1\to t}_{q}$.

\item if $P_S - S^{k+1\to t}_{q} - S^k_q\ge S^{k\to k+1}_{q+1} $ and $P_S - S^{k+1}_q\le S^{k+1\to t}_{q+1}$, then 
$$P^{k\to k+1} + P^{k+1\to t} = S^{k\to k+1}_{q+1} + (P_S - S^{k+1}_q) = $$
$$(P_S - S^{k}_q)  + (S^{k\to k+1}_{q+1} - S^{k\to k+1}_{q})\ge (P_S - S^{k}_q) \ge P^{k\to t} $$
since $S^{k\to k+1}_{q+1}\ge S^{k\to k+1}_{q} $.

\item if $P_S - S^{k+1\to t}_{q} - S^k_q\le S^{k\to k+1}_{q+1} $ and $P_S - S^{k+1}_q\le S^{k+1\to t}_{q+1}$, then 
$$P^{k\to k+1} + P^{k+1\to t} = (P_S - S^{k+1\to t}_{q} - S^k_q) + (P_S - S^{k+1}_q) =
$$
$$ (P_S - S^{k}_q) + (P_S - S^{k+1}_q - S^{k+1\to t}_{q}) \ge (P_S - S^{k}_q) \ge P^{k\to t} $$
 since $P_S \ge S^{k+1}_q + S^{k+1\to t}_{q} = S^t_q $.

\end{enumerate}
So we have proven that the payment can only grow by splitting a conversion market.
\end{proof}

We conclude that the cost of one unit of $C^t$ is never smaller than $P_S$, since by the first lemma, it is true if there was only one conversion, and by induction and the second lemma, splitting the conversion market into all $t-1$ conversion markets can only increase the cost.
\end{proof}

\vskip 0.2in
\bibliography{babaioff2004a}
\bibliographystyle{theapa}


\end{document}


