\section{Introduction}
Modern production is highly interconnected and many firms have a large numbers of buyers and suppliers.
In this paper, we study the structure of contract relationships between firms. In our model, firms have heterogeneous preferences over bilateral
contracts with other firms. Contracts may encode many dimensions of a
relationship including the quantity of a good traded, time of delivery,
quality, and price. The universe of possible relationships between
firms is described by a \textit{contract network} -- a multi-sided matching
market in which firms form downstream contracts to sell outputs and
upstream contracts to buy inputs.

We focus on the existence and structure of stable outcomes in decentralized,
real-world matching markets. In production networks that we consider in
this paper, stable outcomes play the role of an equilibrium concept
and may serve as a reasonable prediction of the outcome of market interactions
\citep{Fox:10}.\footnote{The ``market design'' literature has emphasized the importance of the existence of stable
outcomes in order to prevent centralized matching markets from unraveling
\citep{Roth:91}. While much of this paper is inspired by this line of
research, we do not focus on practical market design applications here.}
We find a general result: any contract network has an outcome that satisfies a
natural extension of \textit{pairwise stability} \citep{GaSh:62}. Our model of
matching markets subsumes many previous models of matching with contracts,
including many-to-one \citep{GaSh:62,CrKn:81,KeCr:82,HaMi:05} and
many-to-many matching markets
\citep{Roth:84,Soto:99,Soto:04,EcOv:06,KlWa:09}.

We build on a seminal contribution by \citet{Ostr:08}, who introduced a matching model
of \textit{supply chains}. In a supply chain, there are agents, who
only supply inputs (e.g. farmers); agents, who only buy final outputs
(e.g. consumers); while the rest of the agents are intermediaries,
who buy inputs and sell outputs (e.g. supermarkets). All agents are
partially ordered along the supply chain: downstream (upstream)
firms cannot sell to (buy from) firms upstream (downstream) i.e. the
contract network is \textit{acyclic}. His key assumption about the market, which we retain in his paper, was that
firms' choice functions over contracts satisfy  \textit{same-side
  substitutability} and \textit{cross-side complementarity} conditions
(\citet{HaKo:12} later called these conditions \textit{full substitutability}).  This assumption requires that firms view any downstream or any
upstream contracts as substitutes, but any downstream and any upstream
contract as complements.%
\footnote{Same-side substitutability is a fairly strong assumption as, for
  example, it rules out any complementarities in inputs. There is evidence
  that modern manufacturing firms rely on many complementary inputs
  \citep{MiRo:90,Fox:10}. \citet{HaKo:15} consider a multilateral matching market with complements when utility is quasilinear in prices. \citet{AlTe:15} analyze supply chains in which inputs could be complementary or substitutable with general preferences. } \citet{Ostr:08} showed that
any supply chain has a \textit{chain-stable} outcome for which there
are no blocking downstream chains of contracts. \citet{HaKo:12} further showed that, in the presence
of network acyclicity, chain-stable outcomes are equivalent to (what we call)
\textit{set-stable}
outcomes i.e. those that are immune to deviations by arbitrary sets of firms. \ch{Even under full substitutability, chain-stable/set-stable outcomes in general supply chains may be Pareto inefficient.\footnote{Inefficiency arises even in two-sided many-to-many matching markets without contracts: \citet{Blai:88} and \citet[p. 177]{RoSo:90} provide the earliest examples; \citet{EcOv:06,KlWa:09} discuss the setting with contracts. \citet{West:10} provides necessary and sufficient conditions on the structure contract relationships in the supply chain for chain-stable outcomes to be efficient.} }

While a supply chain may be a good model of production in certain industries
\citep{AnCh:13}, in general, firms simultaneously supply inputs to\textit{
  and} buy outputs from other firms (possibly through intermediaries). If
this is the case, we say a contract network contains a contract \textit{cycle}.  For
example, the sectoral input-output network of the U.S. economy, illustrated
by \citet[Figure 3]{AcCaOzTa:12}, shows that American firms are very
interdependent and the contract network contains many cycles. Consider a
coal mine that supplies coal to a steel factory.  The factory uses coal to
produce steel, which is an input for a manufacturing firm that sells mining
equipment back to the mine. This creates a contract cycle. However, \citet{HaKo:12}
showed that if a contract network has a contract cycle then set-stable
outcomes may fail to exist. Our first result shows that checking whether an outcome is in fact set-stable is computationally hard. We then show that, even in the presence of contract cycles,
outcomes that satisfy a weaker notion of stability -- \textit{trail
  stability} -- can still be found. A trail of contracts is a sequence of distinct contracts in which a seller (buyer) in one contract is a buyer (seller) in the subsequent one. We argue that trail stability is a useful, natural and intuitive
equilibrium concept for the analysis of matching markets in networks. Along
a blocking trail, firms make unilateral offers to their neighbors while
conditionally accepting a sequence of previous pairwise blocks. Firms can
receive several offers along the trail.  Trail-stable outcomes rule out any
sequence of such consecutive pairwise blocks. Trail stability is equivalent to chain
stability (and therefore to set stability under our assumptions) in acyclic contract networks and to pairwise stability in
two-sided many-to-many matching markets with contracts. Unsurprisingly, therefore, trail-stable outcomes may also be Pareto inefficient \citep{Blai:88}.

In order to analyze properties of trail-stable outcomes, we introduce another stability notion, called \textit{full trail stability}, which does not force intermediary firms to accept all the contracts along a trail, but rather only sign upstream/downstream pairs as they are offered along the trail. We argue that this could also be seen as a useful stability notion for short-run contract relationships. But studying full trail stability also allows us to use familiar fixed-point theorems and other techniques from the matching literature. Fully trail-stable outcomes correspond to the fixed-points of an operator and form a particular lattice structure for \textit{terminal agents}, who can sign only upstream or only downstream contracts. The lattice reflects the classic opposition-of-interests property of two-sided markets, but in our case it is between terminal buyers and terminal sellers. In addition to this strong lattice property, we extend previous results on the existence of buyer- and seller-optimal stable outcomes, the rural hospitals theorem, strategy-proofness as well as comparative statics on firm entry and exit that have only been studied in a supply-chain or two-sided setting under general choice functions (see Figure \ref{generalized}). Fully trail-stable and trail-stable coincide under \textit{separability}, a condition that ensures that decisions over certain pairs of upstream and downstream contracts are taken independently from others. We provide a complete description of the relationships between all stability notions -- set stability, chain stability, trail stability, full trail stability -- that we use in this paper.

Our work complements a recent paper by \citet{HaKoNiOsWe:14} on the properties of set-stable outcomes in general contract networks. They show that in general contract networks, under certain conditions, set-stable outcomes coincide with (what we call) \textit{strongly trail-stable} outcomes i.e. those immune to coordinated deviations by a set of firms which is simultaneously signing a trail of contracts. Our paper is also related to the stability of (continuous and discrete) network flows discussed by \citet{Flei:09,
  Flei:14}. In these models, agents choose the amount of ``flow'' they receive from upstream
and downstream agents and have preferences over who they receive the
``flow'' from. The network flow model allows for cycles. However, the
choice functions in the network flow models are restricted by Kirchhoff's
(current) law (the total amount of incoming (current) flow is equal to the
total amount of outgoing flow) and in the discrete case, these choice
functions are special cases of \citet{Ostr:08}. This paper therefore generalizes both of the supply chain and the network flow models, while offering two appealing new stability concepts.

We also consider a setting in which every contract specifies a trade
and a price. We ask whether there is a competitive equilibrium outcome:
a vector of prices at which agents demand precisely the trades which
are realized. However, to specify competitive equilibrium fully, we
also need to find prices for trades that are not realized. We find
these prices constructively by adapting the salary-adjustment process
of \citet{KeCr:82} and \citet{Roth:84}. While \citet{HaKoNiOsWe:11}
and \citet{HaKo:15} also considered the existence of competitive
equilibrium in general contract networks, in addition to the assumptions
in this paper, they also assumed that firms' profit functions are
\textit{quasilinear} in a continuous numeraire (i.e. there is transferrable
utility). These assumptions not only guarantee the existence, but
also efficiency and stability of competitive equilibrium. However,
the quasilinearity of the firms' profit function is a strong assumption
in many settings. Several reasons for the failure of this assumption
can be found in the empirical literature. First, firms may have financing
constraints since access to debt and equity financing differs across
firms \citep{FaHuPe:88}. Second, firm management may exhibit a version
of the ``wealth effect'' by investing free cash flow into wasteful
investments \citep{Jens:86}. Finally, there is evidence that in volatile
markets firms are risk-averse \citep{Fran:90}. \citet[p. 18]{HaKoNiOsWe:11}
point out that:
\begin{quote}
for contractual sets that allow for continuous transfers, in the presence
of quasilinearity, supply chain structure is not necessary for the
existence of stable outcomes, although full substitutability is. It
is an open question why the presence of a continuous numeraire can
replace the assumption of a supply chain structure in ensuring the
existence of stable outcomes.
\end{quote}
We dispense with quasilinearity entirely while retaining a general
network structure. We establish the existence of competitive equilibrium
in networked markets without transferrable utility under two extra
mild conditions.%
\footnote{There has been relatively little work on the existence of competitive
equilibrium with indivisible goods without transferrable utility,
except in one-to-one markets \citep{Quin:84,Gale:84,DeGa:85,AlJaMa:11,MoSe:14, Heri:15}.%
} The competitive equilibrium outcomes are also trail-stable. \begin{figure}[h]
\begin{tabular}{>{\centering}p{2.9cm}|>{\centering}p{1.4cm}>{\centering}p{1.5cm}>{\centering}p{1.7cm}>{\centering}p{1.3cm}>{\centering}p{2.5cm}>{\centering}p{2.5cm}}
 & {\small{}General networks} & {\small{}General choice\\functions} & {\small{}Competitive equilibrium} & {\small{}Existence and structure} & {\small{}New stability concepts used} & {\small{} Corresponding name in this paper}\tabularnewline
\hline
\hline

{\small{}\citet{Ostr:08}} & \ding{55}\\acyclic & \ding{51} & \ding{55} & \ding{51} & {\small{}Chain-stable} & {\small{}Chain-stable} \tabularnewline
\hline
{\small{}\citet{West:10}} & \ding{55}\\acyclic & \ding{51} & \ding{55} & \ding{51} & {\small{}Group-stable or Setwise-stable,
Core} & -- \tabularnewline
\hline
{\small{}\citet{HaKo:12}} & \ding{55}\\acyclic & \ding{51} & \ding{55} & \ding{51} & {\small{}Stable or Weak Setwise-stable} & {\small{}Set-Stable}\tabularnewline
\hline
{\small{}\citet{HaKoNiOsWe:11}, \citet{HaKo:15}}  & \ding{51} & \ding{55}\\quasilinear & \ding{51} & \ding{51} & {\small{}Strong group-stable} & -- \tabularnewline
\hline
{\small{}\citet{HaKoNiOsWe:14}} & \ding{51} & \ding{51}\\ & \ding{51} & \ding{55}\\ & {\small{}Chain-stable} & {\small{}Strong trail-stable}\tabularnewline
\hline
{\small{}This paper} & \ding{51} & \ding{51} & \ding{51} & \ding{51} & {\small{}Trail-stable,}\\ {\small{}Fully trail-stable} & {\small{}Trail-stable,}\\ {\small{}Fully trail-stable}\tabularnewline
\end{tabular}
\protect\caption{Relationship to previous work.\label{contribution}}
\end{figure}

\begin{figure}[h]
\begin{tabular}{>{\centering}p{6cm}|>{\centering}p{2cm}>{\centering}p{4cm}>{\centering}p{5cm}}
Paper & Theorem & Description & Generalization in this paper \tabularnewline
\hline
\hline
\citet{Ostr:08} & Theorem 1 & Existence of stable outcomes & Theorem \ref{theorem:on-odd-cycle-contracts} and Lemma \ref{main} \tabularnewline
\hline
\citet{HaKo:12} & Theorem 4 & Buyer- and seller-optimality & Lemma \ref{weaker-lattice} and Lemma \ref{fully-stable-lattice} \tabularnewline
\hline
\citet{HaKo:12} & Theorem 8 & Rural hospitals theorem & Proposition \ref{rural} \tabularnewline
\hline
\citet{HaKo:12}  & Theorem 10 & Strategy-proofness & Proposition \ref{Strategyproof} \tabularnewline
\hline
\citet{Ostr:08} & Theorem 3  & Firm entry & Proposition \ref{ostrovsky} \tabularnewline
\hline
\citet{HaKo:13} & Theorem & Vacancy chain dynamics & Proposition \ref{vacancy} \tabularnewline
\hline
\citet{HaKoNiOsWe:11} & Theorem 1 & Competitive equilibrium & Theorem \ref{EquilibriumTheorem}
\tabularnewline
\end{tabular}
\protect\caption{Previous results generalized in this paper to a trading network setting with general choice functions. \label{generalized}}
\end{figure}

Figure \ref{contribution} summarizes stability concepts, results and nomenclature used in this paper with reference to previous work, while Figure \ref{generalized} describes which previous results we have generalized in our setting of trading network with general choice functions.
We proceed as follows. In Section \ref{modelsec}, we present the ingredients of the
model, including the contract network, restrictions on firms choices of contracts, and various stability concepts. In Section  \ref{stabconcepts}, we show that set stability is computationally intractable in general contract networks. Then, in Section \ref{stabsec},
we state our key result of trail-stable outcomes in general contract
networks. We then introduce full trail stability and dig deeper into the structure of fully trail-stable outcomes in
Section \ref{ratsec}. We conclude this section by describing overall relationship between different stability notions.
In Section \ref{equilibsec}, we
show how to construct competitive equilibrium allocations in a model with
prices. Finally, we conclude and outline some directions for future
work. The proofs are in the Appendix.

\section{Model}\label{modelsec}

\subsection{Ingredients}

There is finite set of agents (firms or consumers) $F$ and a finite
set of contracts (contract network) $X$.%
\footnote{The standard justification for this assumption is given by \citet[p. 49]{Roth:84}:
``elements of a {[}contract{]} can take on only discrete values;
salary cannot be specified more precisely than to the nearest penny,
hours to the nearest second, etc.'' In fact, the finiteness assumption is not
necessary for our proofs. We only require that the set of contracts
between any two agents forms a lattice.
} A contract $x\in X$ is a bilateral agreement between a buyer $b(x)\in F$
and a seller $s(x)\in F$. Hence, $F(x)\equiv\{s(x),b(x)\}$ is the
set of firms associated with contract $x$ and, more generally, $F(Y)$
is the set of firms associated with contract set $Y\subseteq X$.
Call $X^B_{f}\equiv\{x\in X|b(x)=f\}$ and $X^S_{f}\equiv\{x\in X|s(x)=f\}$
the sets of $f$'s upstream and downstream contracts -- for which
$f$ is a buyer and a seller, respectively. Clearly, $Y^B_{f}$ and
$Y^S_{f}$ form a partition over the set of contracts $Y{}_{f}\equiv\{y\in
Y|f\in F(y)\}$
which involve $f$, since an agent cannot be a buyer and a seller
in the same contract.

We can show graphically that our structure is more general than the
setting described by \citet{Ostr:08} or \citet{HaKo:12}. Each firm $f\in F$ is associated
with a vertex of a directed multigraph $(F,X)$ and each contract
$x\in X$ is a directed edge of this graph. For any $f$, $X^B_{f}$
is represented by a set of incoming edges and $X^S_{f}$ is represented
by outgoing edges. In Figure \ref{fig:Supply-chain}, we illustrate
a three-level supply chain with two producers, two intermediaries
and two final consumers. Supply chains require a partial order on
the firms' positions in the chain although firms may sell to (buy
from) any downstream (upstream) level. Hence, in Figure \ref{fig:Supply-chain},
the right producer sells directly to the left consumer bypassing the
intermediary. In our model, we consider general contract networks,
which may contain contract cycles (i.e. directed cycles on the graph),
illustrated in Figure \ref{fig:Contract-network}.

\begin{figure}
\begin{minipage}{.5\textwidth}
\begin{centering}
\par\end{centering}
\centering{}
\scalebox{1}{\includegraphics{supplychain}}
\protect\caption{Supply chain\label{fig:Supply-chain}}
\end{minipage}
\begin{minipage}{.5\textwidth}
\begin{centering}
\par\end{centering}
\centering{}
\scalebox{1}{\includegraphics{network}}
\protect\caption{Contract network\label{fig:Contract-network}}
\end{minipage}
\end{figure}

Every firm has a choice function $C^{f}$, such that $C^{f}(Y_{f})\subseteq Y_{f}$
for any $Y_{f}\subseteq X_{f}$.\footnote{Since firms only care about their own contracts, we can write $C^{f}(Y)$ to mean $C^{f}(Y_{f})$.} We say that choice functions of $f\in F$ satisfy the \textit{irrelevance of rejected contracts (IRC)} condition if for any $Y\subseteq X$ and $C^{f}(Y)\subseteq Z\subseteq Y$ we have that $C^{f}(Z)=C^{f}(Y)$ \citep{Blai:88,Alka:02,Flei:03,Eche:07,AySo:12}.\footnote{In our setting IRC is equivalent to the Weak Axiom of Revealed Preference \citep{Alva:15a}.}.

For any $Y\subseteq X$ and $Z\subseteq X$, define the \textit{chosen}
set of upstream contracts
\begin{equation}
C_{B}^{f}(Y|Z)\equiv C^{f}(Y^B_f\cup Z^S_f)\cap X^B_f
\end{equation}
which is the set of contracts $f$ chooses as a buyer when $f$ has
access to upstream contracts $Y$ and downstream contracts $Z.$ Analogously,
define the chosen set of downstream contracts
\begin{equation}
C_{S}^{f}(Z|Y)\equiv C^{f}(Z^S_f \cup Y^B_f)\cap X^S_f
\end{equation}
Hence, we can define \textit{rejected} sets of contracts $R_{B}^{f}(Y|Z)\equiv Y_f\setminus C_{B}^{f}(Y|Z)$
and $R_{S}^{f}(Z|Y)\equiv Z_f\setminus C_{S}^{f}(Z|Y)$. An \textit{outcome}
$A\subseteq X$ is a set of contracts.

A set of contracts $A\subseteq X$ is \textit{individually rational} for an agent $f\in F$ if $C^{f}(A_{f})=A_{f}$. We call set $A$ \textit{acceptable} if $A$ is
individually rational for all agents $f\in F$. For sets of
contracts $W,A\subseteq X$, we say that $A$ is \textit{$(W,f)$-rational} if
$A_{f}\subseteq C^f(W_{f}\cup A_{f})$ i.e. if the agent $f$ chooses all
contracts from set $A_f$ whenever she is offered $A$ alongside
$W$. Set of contracts $A$ is \textit{$W$-rational} if $A$ is $(W,f)$-rational
  for all agents $f\in F$. Note that contract set $A$ is individually rational for agent $f$ if and only if it is
  $(\emptyset,f)$-rational. If $y\in X^B_f$ and $z\in X^S_f$ then $\{y,z\}$ is a
  \textit{$(W,f)$-rational pair} if neither $x$ nor $z$ is $(W,f)$-rational
  but $\{y,z\}$ is $(W,f)$-rational. Note that any rational pair consists
  of exactly one upstream and one downstream contract.

\subsection{Assumptions on choice functions}

We can now state our key assumption on choice functions introduced by \citet{Ostr:08}.
\begin{definition}

Choice functions of $f\in F$ are \textit{fully
substitutable} if for all $Y'\subseteq Y\subseteq X$ and $Z'\subseteq Z\subseteq X$
they are:
\begin{enumerate}
\begin{minipage}{.5\textwidth}
\item \textit{Same-side substitutable} (SSS):

\begin{enumerate}
\item $R_{B}^{f}(Y'|Z)\subseteq R_{B}^{f}(Y|Z)$
\item $R_{S}^{f}(Z'|Y)\subseteq R_{S}^{f}(Z|Y)$
\end{enumerate}
\end{minipage}
\begin{minipage}{.5\textwidth}
\item \textit{Cross-side complementary} (CSC):

\begin{enumerate}
\item $R_{B}^{f}(Y|Z)\subseteq R_{B}^{f}(Y|Z')$
\item $R_{S}^{f}(Z|Y)\subseteq R_{S}^{f}(Z|Y')$
\end{enumerate}
\end{minipage}
\end{enumerate}
\end{definition}

Contracts are fully substitutable if every firm regards any of its
upstream or any of its downstream contracts as substitutes, but its
upstream and downstream contracts as complements. Hence, rejected
downstream (upstream) contracts continue to be rejected whenever the
set of offered downstream (upstream) contracts expands or whenever
the set of offered upstream (downstream) contracts shrinks.

We also introduce a new restriction on choice functions that will play a major role in linking together various stability concepts described in this paper.

\begin{definition}
Choice functions of $f\in F$ are \textit{separable} if for any  $A,W\subseteq X$ and $y\in X^B_f \setminus A$ and $z\in X^S_f \setminus A$, whenever $A$ is $(W,f)$-rational, and $\{y,z\}$ is a $(W,f)$-rational pair, then $A\cup\{y,z\}$ is $(W,f)$-rational.

\end{definition}

Separable choice functions impose a kind of independence on choices of pairs of upstream and downstream contracts. It says that whenever the firm chooses $A$ alongside some set $W$ and $\{y,z\}$ alongside $W$ (but $y$ and $z$ would not be chosen separately alongside $W$ since  $\{y,z\}$ is a $(W,f)$-rational pair), then it would choose $A\cup\{y,z\}$ alongside $W$. Suppose signing $A$ and $\{y,z\}$ are decisions made by separate units of the firm. Separable choice functions say that it can delegate the joint input-output decisions to the units because its overall choices do not require any coordination between the units. One natural example of separable choice functions is the following: suppose each firms totally orders individual upstream contracts and individual downstream contracts. Whenever a firm is offered $k$ downstream and $l$ upstream contracts, it chooses the $z$ best upstream and the $z$ best downstream contracts where $z=\min(k,l)$. \ch{As the example shows, separability is closely resembles `responsiveness'' in the contract network setting \citep{Roth:85b}. It is worth noting, however, that separability, unlike responsiveness, does not imply full substitutability.}

\subsection{Laws of Aggregate Demand and Supply}
We first re-state the familiar Laws of Aggregate Demand and Supply (LAD/LAS) \citep{HaMi:05,HaKo:12}. LAD (LAS) states that when a firm has more upstream (downstream) contracts available (holding the same downstream (upstream) contracts), the number of downstream (upstream) contracts the firms chooses does not increase more than the number of upstream (downstream) contracts the firm chooses. Intuitively, an increase in the availability of contracts on one side, does not increase the difference between the number of contracts signed on either side.
\begin{definition}

Choice functions of $f\in F$ satisfy the Law of Aggregate Demand if for all $Y,Z\subseteq X$
and $Y'\subseteq Y$

\[
|C_{B}^{f}(Y|Z)|-|C_{B}^{f}(Y'|Z)|\geq|C_{S}^{f}(Z|Y)|-|C_{S}^{f}(Z|Y')|
\]

and the Law of Aggregate Supply if for all $Y,Z\subseteq X$ and $Z'\subseteq Z$

\[
|C_{S}^{f}(Z|Y)|-|C_{S}^{f}(Z'|Y)|\geq|C_{B}^{f}(Y|Z)|-|C_{B}^{f}(Y|Z')|
\]

\end{definition}

We can easily show that LAD/LAS imply IRC, extending the result by \citet{AySo:12}.

\begin{lemma}\label{ladlasirc} In any contract network $X$ if choice functions of $f \in F$ satisfy full substitutability and LAD/LAS then the choice functions of $f$ satisfy IRC.
\end{lemma}

\subsection{Terminal agents and terminal superiority}
We now introduce some terminology that describes contracts of agents, who only act as buyers or only act as sellers. A firm $f$ is a \textit{terminal seller} if there are no upstream contracts for $f$ in
the network and $f$ is a \textit{terminal buyer} if the network does not contain
any downstream contracts for $f$. An agent who is either a terminal buyer or a terminal seller is called a \textit{terminal agent}. Let $\mathcal{T}$ denote the set of terminal agents in $F$ and for a set $A$ of contracts let
us denote the \emph{terminal contracts of $A$}
\ch{ by $A_\mathcal{T}:=\bigcup \{A_f|f\in \mathcal{T}\}$. }A set $Y$
of contracts is \emph{terminal-acceptable} if there is an acceptable set
$A$ of contracts such that $Y=A_\mathcal{T}$. If $A$ and $W$ are terminal-acceptable sets of contracts
then we say that $A$ is \textit{seller-superior} to $W$ (denoted by
$A\succeq^S W$) if $C_f(A_f\cup W_f)=A_f$ for each terminal seller $f$ and
$C_g(A_g\cup W_g)=W_g$ for each terminal buyer $g$. Similarly, $A$ is
\textit{buyer-superior} to $W$ (denoted by $A\succeq^B W$) if $C_f(A_f\cup
W_f)=W_f$ for each terminal seller $f$ and $C_g(A_g\cup W_g)=A_g$ for each
terminal buyer $g$. Clearly, these relations are opposite, that is, $W\succeq^S
A$ if and only if $A\succeq^B W$ holds. Whenever either relation holds, we call this partial order on outcomes \textit{terminal superiority}. \ch{Terminal agents are going to play a key role when we describe the structure of outcomes in contract networks.}

\subsection{Stability concepts}\label{stabconcepts}

We start off by defining two stability notions that have appeared in previous work.

\begin{definition} An outcome $A\subseteq X$ is \textit{set-stable}\footnote{\citet{KlWa:09} call set-stable outcomes ``weak setwise stable'' and \citet{HaKo:12} call them ``stable'': we take the middle ground. \citet{West:10} applies the label ``group stable'' to ``setwise stable outcomes'' \citep{Soto:99,EcOv:06,KlWa:09}.} if:
\begin{enumerate}
\item $A$ is acceptable.
\item There exist no non-empty blocking set of contracts $Z\subseteq X$, such that $Z\cap A=\emptyset$ and $Z$ is $(A,f)$-rational for all $f\in F(Z)$.
\end{enumerate}
\end{definition}

Set-stable outcome are immune to deviations by \textit{sets} of firms, which can re-contract freely among themselves while keeping any of their existing contracts. Set-stable outcomes always exist in acyclic networks if choice functions are fully substitutable. In order to study more general contract networks, we first introduce trails of contracts.

\begin{definition}
A non-empty sequence of different contracts $T=\{x_{1},\ldots,x_{M}\}$ is a
\textit{trail} if
$b(x_{m})=s(x_{m+1})$ holds for all $m=1,\ldots,M-1$.
\end{definition}

While a trail may not contain the \ch{same contract more than
once}, it may include the same agents any number of times.
Figure
\ref{fig:Contract-network} illustrates a trail that starts from firm $i$ to firm $j$ via firm $k$. A trail $T$ is
a \textit{chain} if all the agents $F(T)$ involved in the trail are distinct.
A chain from firm $i$ to firm $j$ is illustrated in Figure \ref{fig:Supply-chain}.

\begin{definition} An outcome $A\subseteq X$ is \textit{strongly trail-stable} if
\begin{enumerate}
\item $A$ is acceptable.
\item There is no trail $T$, such that $T\cap A=\emptyset$ and $T$ is $(A,f)$-rational for all $f\in F(T)$.
\end{enumerate}
\end{definition}

\citet{HaKoNiOsWe:14} showed that in general contract networks set-stable
outcomes are equivalent to strongly trail-stable outcomes whenever choice functions satisfy full substitutability and Laws of
Aggregate Demand and Supply.\footnote{\citet{HaKoNiOsWe:14} call trails
  ``chains'' and strong trail stability ``chain stability''. We use our
  terminology to avoid the confusion with the original definition of ``chains''
  and ``chain stability'' in \citet{Ostr:08}. Our distinction between ``trails'' and ``chains'' (or ``paths'') is used in most graph theory textbooks. } However, \citet{Flei:09} and
\citet{HaKo:12} showed that a set-stable outcomes may not exist in
general contract networks (see Example \ref{trail-not-group-stable-example}
below). Moreover, our first result demonstrates that set stability is
computationally intractable. Let us define decision problem GS as
follows. An instance of GS is a
trading network with a set of agents $F$ and set of contracts $X$ (with choice functions that satisfy full substitutability and IRC) and an outcome $A$. The answer for an instance of GS is YES if the particular outcome $A$ is not set-stable (that is, if there is a set of contracts $Z$ that blocks $A$),
otherwise the answer is NO.

\begin{theorem}\label{grouphopeless}
Problem $GS$ is NP-complete. Moreover, if choice functions are represented by
oracles then finding the right answer for an instance of GS might need an
exponential number of oracle calls.
\end{theorem}

The non-existence of set-stable outcomes and their computational intractability motivates us to define a less restrictive stability notions.

We first define \textit{trail stability}, which coincides with pairwise stability
in a two-sided many-to-many matching market with contracts \citep{Roth:84}
and with chain stability in supply chains \citet[p. 903]{Ostr:08}.
Define $T_{f}^{\le m}=\{x_{1},...,x_{m}\}\cap T_{f}$ to be firm $f$'s contracts out of the first $m$ contracts in the trail
and $T_{f}^{\ge m}=\{x_{m},...,x_{M}\}\cap T_{f}$ to be firm $f$'s contracts out of the last $M-m+1$
contracts in the trail.

\begin{definition}\label{trailstable} An outcome $A\subseteq X$ is \textit{trail-stable} if
\begin{enumerate}
\item $A$ is acceptable.
\item There is no trail $T=\{x_1,x_2,\ldots,x_M\}$, such that $T\cap
  A=\emptyset$  and
\begin{enumerate}
\item $x_1$ is $(A,f_1)$-rational for $f_1=s(x_{1})$ and
\item At least one of the following two options holds:
\begin{enumerate}
\item   $T_{f_{m}} ^{\le m}$ is
$(A,f_m)$-rational for $f_m=b(x_{m-1})=s(x_{m})$ whenever $1<m\le M$, or
\item $ T_{f_{m}}^{\ge m-1}$ is
$(A,f_m)$-rational for $f_m=b(x_{m-1})=s(x_{m})$ whenever $1<m\le M$
\end{enumerate}
\item $x_M$ is $(A,f_{M+1})$-rational for $f_{M+1}=b(x_{M})$.
\end{enumerate}
The above trail $T$ is called a \textit{blocking trail to $A$}.

\end{enumerate}

\end{definition}

Trail stability is a natural stability concept when firms interact
mainly with their buyers and suppliers and deviations by arbitrary
sets of firms are difficult to arrange. In a trail-stable outcome,
no agent wants to drop his contracts and there exists no set
 of \textit{consecutive}
bilateral contracts comprising a trail preferred by all the agents
in the trail to the current outcome.
First, $f_{1}$ makes an unilateral offer of $x_{1}$ (the first contract
in the trail) to the buyer $f_{2}$. At this stage seller $f_{1}$
does not consider whether he may act as a buyer or a seller in the
trail again (in that sense the deviations are pairwise and consecutive).
The buyer $f_{2}$ then either unconditionally accepts the offer (forming
a blocking trail) or conditionally accepts the seller's offer while
looking to offer a contract ($x_{2}$) to another buyer $f_{3}$.
If $f_{2}$'s buyer in $x_{2}$ happens to be $f_{1}$, then $f_{1}$
considers the offer of $x_{2}$ together with $x_{1}$ (which he has
already offered). If $f_{1}$ accepts, we have a blocking trail. If $f_{2}$'s
buyer is not $f_{1}$, then his buyer either accepts $x_{2}$ unconditionally
or looks for another seller $f_{4}$ after a conditional acceptance
of $x_{2}$. The trail of ``conditional'' contracts continues until
the last buyer $f_{M+1}$ in the trail unconditionally accepts the
upstream contract offer $x_{M}$.%
\footnote{The trail and the order of conditional acceptances can, of course,
be reversed with $f_{M+1}$ offering the first upstream contract to
seller $f_{M}$ and so on. %
} Note that as the blocking trail grows, we ensure that each intermediate
agent wants to choose all his contracts along the trail.

In general, trail stability is a weaker stability notion than set
stability. The following example illustrates that trail-stable outcomes are not necessarily set-stable.\footnote{This is similar to examples in \citet[p. 12]{Flei:09} and \citet[Fig. 3, p. 13]{HaKo:12}.}

\begin{figure}
\centering{}\scalebox{1}{\includegraphics{trailstabs}}
\protect\caption{Example of a network that is trail-stable, but not
  set-stable\label{fig:hatkom}}
\end{figure}
\begin{example}[Trail-stable outcomes are not necessarily set-stable] \label{trail-not-group-stable-example}
Consider four contracts $x$, $y$, $z$ and $m$. Assume that $i=b(x)$, $j=s(x)=s(z)=b(y)=b(w)$,
$k=b(z)=s(y)$ and $m=s(w)$ (see Figure \ref{fig:hatkom}).
Agents have the following preferences that induce fully substitutable choice functions:\footnote{In all our examples, $\succ$ denotes a strict preference relation. Choice function induced by strict preferences satisfy IRC. \info{We say that $f \in F$ ``prefers'' outcome $A$ to outcome $A'$ if $C^f(A\cup A')=A_f$} }\\
$\succ_{i}:\{x\}\succ_{i}\emptyset$\\
$\succ_{m}:\{w\}\succ_{m}\emptyset$\\
$\succ_{j}:\{x,y,w\}\succ_{j}\{z,y,w\}\succ_{j}  \{x,y\}\succ_{j}\{z,y\}\succ_{j}\{w\}\succ_{j}\emptyset$\\
$\succ_{k}:\{z,y\}\succ_{k}\emptyset$.\\
Hence, a trail-stable outcome exists: $A=\{w\}$.%
\footnote{An outcome $A$ is chain-stable if $A$ is acceptable and there are no blocking chains \citep{Ostr:08}. Therefore, $\{w\}$ is also the unique chain-stable outcome.%
} The trail-stable outcome is Pareto inefficient as $\{w\}$ is the least preferred outcome for all agents. There is, however, no set-stable outcome.%
\footnote{Because $\{w\}\succ_{j} \{x,w\}\succ_{k} \{x,z,w\}\succ_{i,j} \{z,y,w\}\succ_{j,k} \{w\}$
and other outcomes are not acceptable.%
}
\end{example}

To illustrate trail stability further, let us drop agents $i$ and $m$ and their corresponding contracts from
the example above.
\ch{ The  new preferences of $j$ are $\{y,z\}\succ_{j}\emptyset$. }  There is one set-stable outcome $\{y,z\}$. There are, however,
two trail-stable outcomes: $\emptyset$ and $\{y,z\}$. Is $\emptyset$
a reasonable possible outcome of this market? We argue that, in a
variety of richer economic models of contracts, it may well be. Suppose
that firms are unable to have a joint meeting and must resort to making
a unilateral offers. Either firm may be reluctant to make the first
offer because in absence of the counteroffer it could end up revealing
sensitive information about its costs. Therefore, firms are unable
to coordinate $\{y,z\}$ and are stuck in the ``inefficient equilibrium''.
As such, trail stability provides a natural solution concept for
matching markets in which firms have limited ability to coordinate their
decisions in the contract network.

\section{Existence and properties of stable outcomes}\label{stabsec}
We can now state the first key result of this paper.
\begin{theorem}\label{theorem:on-odd-cycle-contracts}
In any contract network $X$ if choice functions of $F$ are fully substitutable and satisfy IRC then there exists a trail-stable outcome $A\subseteq X$. \end{theorem}
This theorem establishes a positive existence result for stable outcomes in general contract networks: under the usual assumptions, trail-stable outcomes always exist.\footnote{Since trail stability is, in general, stronger than chain stability, Theorem \ref{theorem:on-odd-cycle-contracts} also implies than any contract network has a chain-stable outcome. Our results do not contradict Theorem 5 on the non-existence of set-stable outcomes in \citet{HaKo:12} since Theorem \ref{theorem:on-odd-cycle-contracts} only considers the existence of trail-stable outcomes.}

\subsection{Fully trail-stable outcomes}\label{ratsec}

In order to examine the structure of trail-stable outcomes, we need to introduce another stability notion.

\begin{definition} An outcome $A\subseteq X$ is \textit{fully trail-stable} if
\begin{enumerate}
\item $A$ is acceptable.
\item There is no trail $T=\{x_1,x_2,\ldots,x_M\}$, such as $T\cap
  A=\emptyset$  and
\begin{enumerate}
\item$x_{1}$ is $(A,f_1)$-rational for $f_{1}=s(x_{1})$, and
\item$\{x_{m-1}\cup x_{m}\}$ is $(A,f_m)$-rational for
$f_{m}=b(x_{m-1})=s(x_{m})$ whenever $1<m\le M$ and
\item$x_{M}$ is $(A,f_M)$-rational for $f_{M+1}=b(x_{M})$.
\end{enumerate}
The above trail $T$ is called a \textit{locally blocking trail to
  $A$}.
\end{enumerate}

\end{definition}

Full trail stability may, at first glance, appear to be an unappealing stability concept. While it rules out (locally) blocking trails, it does not require, as trail stability, that agents accept all their contracts along such blocking trails. More formally, a locally blocking trail may not be an acceptable blocking trail. However, full trail stability has an interesting and important economic interpretation.
Suppose contracts only need to be fulfilled sequentially i.e. once a firm's upstream contract has been fulfilled, it immediately fulfils its downstream contract.\footnote{Alternatively, contracts further down the trail could be specified to be fulfilled later.} This is a natural assumption in sequential production networks as production may not be able to continue without inputs and inputs would not be bought without a standing order. Then firms do not need to worry about being involved in multiple chains of contracts along the trail since they never need to be fulfilled together. As such full trail stability can be a useful stability concept in production networks in which production is sequential rather than (possibly) simultaneous. Full trail stability may be a better stability concept for a short-run prediction of network stability whereas trail stability is more suitable for the long run.
It turns out that fully trail-stable outcomes also exist in general production networks.
\begin{lemma}\label{main}
In any contract network $X$ if choice functions of $F$ are fully substitutable and satisfy IRC then there exists a fully trail-stable outcome $A\subseteq X$.
\end{lemma}
In order to prove Lemma \ref{main}, we use tools familiar to matching theory, such as the Tarski fixed-point theorem \citep{Adac:00,Flei:03,EcOv:04,EcOv:06,HaMi:05, Ostr:08, HaKo:12}.
\ch{Let $X^{B}$ and $X^{S}$ be two subsets of $X$ which represent the set of contracts offered to buyers and sellers.  We define an isotone operator $\Phi$ that acts on $(X^{B},X^{S})$ and any fixed-point $(\dot X^{B},\dot X^{S})$ of  $\Phi$  corresponds to a {fully trail}-stable outcome $A=\dot X^{B}\cap \dot X^{S}$.} \ch{These tools allow us to explore properties of fully trail-stable outcomes that have previously only been explored in a supply-chain or a two-sided setting.}
Recall that in the marriage model of Gale and Shapley, the existence of man-optimal and woman-optimal stable matchings follow from the well-known lattice structure of stable matchings. The key to extending this result to contract networks is to consider only terminal agents. We say that a fully trail-stable outcome $A_{max}$ ($A_{min}$) that is \textit{buyer-optimal} (\textit{seller-optimal}) if any terminal buyer (terminal seller) prefers it to any other outcome i.e. for any fully trail-stable $Z\subseteq X$, we have that $C^f(A_{max}\cup Z)=A_{f,max}$.
\begin{lemma}\label{weaker-lattice}
In any contract network $X$ if choice functions of $F$ are fully substitutable and satisfy IRC then the set of fully trail-stable outcomes contains buyer-optimal and seller-optimal outcomes.
\end{lemma}
Lemma \ref{weaker-lattice} extends Theorem 4 by \citet{HaKo:12}, which establishes the existence of buyer- and seller-optimal outcomes in acyclic trading networks.\footnote{This is a common property of stable outcomes in two-sided markets with substitutable choice functions, however, it typically fails in richer matching models \citep{YePy:15,Alva:15, AlTe:15}.}
We say that $Y\subseteq X$ is \emph{terminal-fully-trail-stable} if there is a fully trail-stable outcome $A\subseteq X$ such that $Y=A_\mathcal{T}$.
\begin{lemma}\label{fully-stable-lattice}
In any contract network $X$ if choice functions of $F$ are fully substitutable and satisfy LAD/LAS then the terminal-fully-trail-stable contract sets form a lattice under terminal superiority. \end{lemma}

Lemma \ref{fully-stable-lattice} shows that whenever LAD/LAS holds choice functions of terminal agents define a natural partial order on outcomes and the terminal-fully-trail-stable contract sets form a lattice under this order. Note that for the lattice and the opposition-of-interests structure, only terminal agents play a role: two outcomes are equivalent if all the terminal agents have the same set of contracts. Indeed, if $A^1$ and $A^2$ are fully trail-stable
outcomes then there is a fully trail-stable outcome $A^{+}$ such that all
terminal buyers prefer $A^{+}$ to both $A^1$ and $A^2$ and all sellers prefer any of
$A^1$ and $A^2$ to $A^{+}$.\footnote{Of course, the same holds for if we exchange the
role of buyers and sellers.} This establishes full ``polarization of interests'' in trail-stable outcomes in the sense of \citep{Roth:85} and immediately implies the existence of buyer-optimal ($A_{max}$) and seller-optimal ($A_{min}$) fully trail-stable outcomes. Therefore, our result substantially strengthens and generalizes the previous results by \citet{Roth:85,Blai:88,EcOv:06} and \citet{HaKo:12}.\footnote{
\ch{ Theorem 4 in \citet{Flei:14}, which states that any two stable flows agree on terminal contracts, is a further strengthening of Lemma \ref{fully-stable-lattice}  in the special case of network flows.}}

The lattice structure of fully-trail stable outcomes allows us to straightforwardly extend two well-known properties of stable outcomes that have been known in two-sided matching markets and acyclic contract networks. One such property is the classic ``rural hospitals theorem'', which shows that in every stable allocation of a two-sided many-to-one doctor-hospital matching market, the same number of doctors are matched to every hospital \citep{Roth:86}. In buyer-seller networks, we can instead consider the difference between the number of upstream and downstream contracts that firms sign \citep{HaKo:12}. The following proposition gives the most general rural hospital theorem result.\footnote{Its proof, which we omit, follows the proof of Theorem 8 in \citet{HaKo:12} word-for-word, only replacing ``stable'' with ``fully trail-stable''.}

\begin{proposition}\label{rural}
Suppose that in a contract network $X$ choice functions of $F$ are fully substitutable and satisfy LAD/LAS. Then, for each firm, the difference between the number of upstream contracts and the number of downstream contracts is invariant across fully trail-stable allocations.
\end{proposition}

The lattice structure of fully trail-stable outcomes also gives a (somewhat weak) mechanism design result. A mechanism $\mathcal{M}$ is a mapping from a profile of agents' choice functions, $\mathbf{C}^F=(C^f)_{f\in F}$, to the set of outcomes.
\begin{definition}
A mechanism is \textit{group strategy-proof} for $G\subseteq F$ if for any $\bar{G}\subseteq G$, there does not exist a choice function profile $\mathbf{\bar{C}}^{\bar{G}}$ such that for outcomes $\bar{A}=\mathcal{M}(\mathbf{\bar{C}}^{\bar{G}}, \mathbf{C}^{F\setminus \bar{G}})$ and $A=\mathcal{M}(\mathbf{C}^{F})$ we have that $C^f(\bar{A}\cup A)=\bar{A}$ for \ch{every} $f\in \bar{G}$.
\end{definition}
A mechanism is group strategy-proof for a group of agents if they cannot jointly manipulate their choice functions and obtain an outcome that is better for all of them. Like \citet{HaKo:12}, we are only going to consider group strategy-proofness for terminal agents. We generalize their Theorem 10 with the following result.
\begin{proposition}\label{Strategyproof}Suppose that in a contract network $X$ choice functions of $F$ are fully substitutable and satisfy LAD/LAS and additionally all terminal buyers (terminal sellers) demand at
most one contract, then any mechanism that selects the buyer-optimal (seller-optimal)
fully trail-stable allocation is group strategy-proof for all terminal buyers. \end{proposition}
As is well known, the assumptions that underpin Proposition \ref{Strategyproof} -- unit demands and extreme one-sidedness -- cannot be substantially relaxed.\footnote{Its proof, which we omit, just follows the proof of Theorem 1 in \citet{HaKo:09} (which was pointed out by \citet{HaKo:12}).}

The second set of properties of fully trail-stable outcomes concerns the effect of entry and exit of new firms in the trading network. This type of comparative static analysis is well-studied in two-sided matching markets \citep{GaSo:85a,Craw:91,BlRoRo:97,HaMi:05}. More recently, \citet{Ostr:08} and \citet{HaKo:13} extended these results the case of supply chains.

First,  let us consider what happens when a terminal seller is added to the
market.
More formally, let $F'= F \cup f'$  and let $A'_{max}$   and $A'_{min}$  be the buyer-optimal and the seller-optimal fully trail-stable outcomes in $F'$ respectively.

\begin{proposition}\label{ostrovsky}
\ch{
Consider a contract network $X$ in which choice functions of $F$ are fully substitutable and satisfy IRC.
Suppose a new terminal seller $f'$ whose choice function is fully substitutable and satisfies IRC enters the market.

Then every terminal seller $f\neq f'$ }is prefers $A_{max}$ to $A'_{max}$ and prefers $A_{min}$ to $A'_{min}$,  and each  terminal buyer $f$ is prefers $A_{max}$ to $A'_{max}$ and prefers $A_{min}$ to $A'_{min}$.\\
The opposite holds when $f'$ is terminal buyer.

\end{proposition}

The proposition says that with a new seller, the seller-optimal outcome $A_{min}$ and the buyer-optimal outcome $A_{max}$ move in the direction favorable to terminal buyers and unfavorable to terminal sellers. Symmetrically, when a terminal buyer is
added or if a seller leaves, $A_{min}$ and $A_{max}$ move in the opposite direction. In other words, more
competition on one end of an industry is bad for the agents on that end and good for the agents
on the other end.  This proposition generalizes Theorem 3 in \citet{Ostr:08}.

Now consider the following \textit{market readjustment process}:
 When the new terminal seller $f'$ enters, \ch{ and we already have a fully trail-stable outcome $A$ with corresponding fixed point $(\dot X^B, \dot X^S)$  then let $X$ be the set of all contracts in the new network, and let us define $(\dot X'^{B},\dot X'^{S})=(\dot X^B, \dot X^S\cup X_{f'})$. Operator $\Phi' $ acts on $(X^{'B},X^{'S})$ using choice functions of $F'$.
Let $(\hat X^B, \hat X^S)$ be the fixed point of the iteration of fuction $\Phi$,
with associated outcome
$ \hat A=\hat X^B \cap \hat X^S$. This $\hat A$ be the result of the market readjustment process.
}

\begin{proposition}\label{vacancy}
Consider a contract network $X$ in which choice functions of $F$ are fully substitutable and satisfy IRC and $A$ is a fully trail-stable outcome with associated buyer and seller offer sets $X^B$ and $X^S$.
Suppose a new terminal seller $f'$ whose choice function is fully substitutable and satisfies IRC enters the market and let $ \hat A$ be the result of the market readjustment process.

Then, all terminal sellers prefer $A$ to $ \hat A$ and all terminal buyers  (other than $f'$) prefer $\hat A$ to $A$.\\
The opposite holds when $f'$ is terminal buyer.
\end{proposition}
An analogous result can be obtained when terminal buyers and terminal sellers exit the market so this proposition generalizes the Theorem in \citet{HaKo:13}.

\subsection{Relationships between stability concepts}
In this section, we link together all the stability concepts discussed above. We first show that set stability implies full trail stability, which in turn implies trail stability. We also link set stability and trail stability via intensity. We then link trail stable and fully trail-stable outcome via separability. Finally, we explore chain stability \citep{Ostr:08}.\\
The follow lemma ties three key stability concepts together.
\begin{lemma}\label{path-path}
In any contract network $X$ if choice functions of $F$ are fully substitutable and satisfy IRC then the following hold for an outcome $A\subseteq X$: \\
 \indent (i) If $A$ is a fully trail-stable outcome then $A$ is also trail-stable. \\
 \indent (ii) If $A$ is a set-stable outcome then $A$ is fully trail-stable.
\end{lemma}
Lemma \ref{main} and Lemma \ref{path-path} immediately imply Theorem \ref{theorem:on-odd-cycle-contracts}. We now pin down the role of separability for trail-stable and fully trail-stable outcomes.
\begin{proposition}\label{fully-vs-trail}
In any contract network $X$ whenever choice functions of $F$ are fully substitutable, separable and satisfy IRC an outcome $A\subseteq X$ is fully trail-stable if and only if it is trail-stable.
\end{proposition}
Under separability all properties of fully trail-stable outcomes apply to trail-stable outcomes. This is summarized in the following corollary.\footnote{
We also conjecture that in any contract network $X$ if choice functions of $F$ satisfy full substitutability and \textit{only} LAD/LAS then the terminal-trail-stable contract sets form a lattice under terminal superiority, but leave this for future work.}
\begin{corollary}
Suppose that in a contract network $X$, choice functions of $F$ are fully substitutable, separable and satisfy IRC.
Then all properties of fully trail-stable outcomes, described in Lemma \ref{weaker-lattice}, Lemma \ref{fully-stable-lattice}, Proposition \ref{rural}, Proposition \ref{Strategyproof}, Proposition \ref{ostrovsky} and Proposition \ref{vacancy}, apply to trail-stable outcomes.
\end{corollary}
Separability is crucial for the correspondence between fully trail-stable and trail-stable outcomes. Separability ensures that all blocking trails are locally blocking trails. An example below shows that full trail stability is strictly stronger that trail stability.
\begin{example}[Trail-stable outcomes are not always fully trail-stable] \label{ex:not-fully-trail-stable}
Consider agents and contracts described in Example 1 and Figure \ref{fig:hatkom}.
Agents have the following preferences that induce fully substitutable choice functions:\\
$\succ_m:\{ w\} \succ_m \emptyset$\\
$\succ_i: \{ x\} \succ_i \emptyset$\\
$\succ_k: \{ z,y\} \succ_k \emptyset$\\
$\succ_j: \{z,y\}\succ_j\{w,z\}\succ_j\{y,x\}\succ_j\emptyset$.\\
The empty set is preferred to any other set of contracts.\\
For outcome $A=\emptyset$, the trail $\{w,z,y,x\}$ is locally blocking
trail but not trail-blocking. Therefore, trail-stable outcomes are
$\emptyset$ and $\{z,y\}$ but the only fully trail-stable outcome is
$\{z,y\}$. Note that $j$'s choice function induced by the preference is not separable.
\end{example}

Finally, we explore the relationship between trail stability, set stability and chain stability.

\begin{definition}
Choice functions of $f\in F$ are \textit{simple} if there exists an ``intensity'' mapping $w:X_f\to {\mathbb R}$ such that whenever $A$ is a $(W,f)$-rational set for some acceptable set $A$ of contracts, then for every $y \in X^B_f \cap A$ there exists  $z \in X^S_f \cap A$ such that $w(y)>w(z)$ holds.
\end{definition}

One example of choice functions which are simple are the following: if the agent is offered a set of contracts, he picks the upstream contract $y$ with the highest intensity and a downstream contract $z$ with the lowest intensity (as long as the intensity of the $y$ is greater than of $z$, otherwise he picks nothing). For example,  if the intensity mapping $w$ represents the per-unit price of the contract, then the condition says that the firm only signs a pair of contracts if the price in the downstream contract is greater than the price in the upstream contract, while picking the highest-price downstream contract and the lowest-price upstream contract.

\begin{proposition}\label{group-vs-trail}
In any contract network $X$ whenever choice functions of $F$ are fully substitutable, simple and satisfy IRC then an outcome $A\subseteq X$ is set-stable if and only if it is trail-stable.
\end{proposition}

We now formally define chain stability, introduced by \citet{Ostr:08}. To recap, a chain $C$ is a trail in which all the agents are distinct. Chain-stable outcomes rule out consecutive pairwise deviations along chains. While this stability concept was introduced in the context of acyclic trading network, it could also be applicable to general trading networks in which firms only have one opportunity to recontract during a deviation.

\begin{definition} An outcome $A\subseteq X$ is \textit{chain-stable} if
\begin{enumerate}
\item $A$ is acceptable.
\item There is no chain $C=\{x_1,x_2,\ldots,x_M\}$, such as $C\cap
  A=\emptyset$  and
\begin{enumerate}
\item$x_{1}$ is $(A,f_1)$-rational for $f_{1}=s(x_{1})$, and
\item$\{x_{m-1}\cup x_{m}\}$ is $(A,f_m)$-rational for
$f_{m}=b(x_{m-1})=s(x_{m})$ whenever $1<m\leq M$ and
\item$x_{M}$ is $(A,f_M)$-rational for $f_{M+1}=b(x_{M})$.
\end{enumerate}
\end{enumerate}

\end{definition}

Since every chain is a trail, every trail-stable outcome is chain-stable. In acyclic networks every trail is also chain, so chain-stable, trail-stable and fully trail-stable outcomes coincide with set-stable outcomes \citep{HaKo:12}. However, as the example below shows, chain stability is weaker than trail stability (and hence weaker than full trail stability) in general contract networks.
\begin{example}[Chain-stable outcomes are not necessarily trail-stable]
Consider agents and contracts described in Examples 1 and 2, and Figure \ref{fig:hatkom}. Agents have the following fully substitutable preferences:\\
$\succ_m:\{ w\} \succ_m \emptyset$\\
$\succ_i: \{ x\} \succ_i \emptyset$\\
$\succ_k: \{ z,y\} \succ_k \emptyset$\\
$\succ_j: \{w,x,z,y\} \succ_j \{w,z\} \succ_j \{y,x\} \succ_j \{y,z\} \succ_j \emptyset$\\
The empty set is preferred to any other set of contracts.\\
Now, for outcome $\emptyset$, the trail $\{w,z,y,x\}$ is  trail-blocking, but there is no blocking chain for $A=\emptyset$.
Outcome $\{z,y\}$  is, however, blocked by chain  $\{w,x\}$.
Therefore the only trail-stable outcome is $\{w,z,y,x\}$ and the chain-stable outcomes are $\emptyset$ and $\{w,z,y,x\}$.
\end{example}

\begin{figure}[t]
\centering{}\scalebox{0.6}{\includegraphics{StabilitiesNonSep}}
\protect\caption{Relationship between stability concepts in general contract networks\label{fig:relationship}}
\end{figure}
This is intuitive because chains allows the firms to appear in the blocking set only once therefore they rule out fewer possible blocks. Figure \ref{fig:relationship} summarizes the relationships between various stability concepts in general contract networks. Set-stable and strongly trail-stable outcomes may not exist and they are only equivalent under the Laws of Aggregate Demand and Supply as Example 1 in \citet{HaKoNiOsWe:14} shows.

\section{Competitive equilibrium}\label{equilibsec}

We now turn to the existence of competitive equilibrium in our model
when each contract specifies a price. We assume that each contract
$(\omega,p_{\omega})\equiv x\in X\equiv\Omega\times\mathbb{Z}$ specifies
a trade $\omega\in\Omega$ and a price $p_{\omega}\in\mathbb{Z}$.%
\footnote{This price can be viewed as a \textit{generalized salary}; see the
discussion by \citet{Roth:84}. Since firms can sign more than one
contract between them, our framework with contracts cannot be embedded
into a framework with prices despite the full substitutability assumption
\citep{Eche:12,Komi:12}.%
} Trades from $\Psi\subseteq\Omega$ involving $f$ are denoted $\Psi_{f}$.
For any $p_{\omega}$, we have $b(\omega)=b(x)$ and $s(\omega)=s(x)$.
Trades associated with contracts $Y$ are denoted $\tau(Y)$. Let
$p$ be $|\Omega|$-dimensional price vector specifying a price for
each trade. A set of contracts $Y\subseteq X$ is feasible if there
is at most one price specified for each trade i.e. there is no trade
$\omega$ and price $p_{\omega}$ and $p'_{\omega}\neq p_{\omega}$
such that $(\omega,p_{\omega})$ and $(\omega,p'_{\omega})$ are in
$Y$. Choice functions are \textit{feasible} if for any $Y\subseteq X$,
$C^{f}(Y)$ is feasible. An arrangement $[\Psi;p]$ is a set of trades
$\Psi\subseteq\Omega$ and a price vector specifying precisely one
price for each trade in the economy. Call $\kappa([\Psi;p])=\cup_{\omega\in\Psi}(\omega,p_{\omega})$
the set of contracts associated with the arrangement $[\Psi;p]$.
Clearly, $\kappa([\Psi;p])$ is feasible. Competitive equilibrium
specifies the allocation of trades and the prices of every trade in
the economy.

\begin{definition}Competitive equilibrium is an arrangement $[\Psi^{*};p^{*}]$
such that for all $f\in F$, $\kappa([\Psi_{f}^{*},p^{*}])=C^{f}(\kappa([\Omega,p^{*}]))$.
\end{definition}

We can construct a competitive equilibrium outcome (i.e. a feasible
set of contracts) from any competitive arrangement by associating
the contracts with the realized trades at competitive equilibrium
prices. In order to ensure that prices are indeed assigned to every
trade, we introduce two further assumptions:

\begin{definition}\textit{Complete prices} (CP): $ $For every $\omega\in\Omega$:
\begin{enumerate}
\item There exists a price $\hat{p}_{\omega}$ such that whenever $f=b(\omega)$,
$ $$(\omega,\hat{p})\in C^{f}((\omega,\hat{p})\cup Y)$ for any $Y\subseteq X$.
\item There exists a price $\check{p}_{\omega}$ such that whenever $f=s(\omega)$,
$ $$(\omega,\check{p})\in C^{f}((\omega,\check{p})\cup Y)$ for any
$Y\subseteq X$.
\item Whenever $(\omega,p_{\omega})\in R^{s(\omega)}((\omega,p_{\omega})\cup Y)$
and $(\omega,p_{\omega})\in R^{b(\omega)}((\omega,p_{\omega}+1)\cup Y)$,
there exists a price $p_{\omega}\leq\tilde{p}_{\omega}\leq p_{\omega}+1$,
such that $(\omega,\tilde{p})\in R^{b(\omega)}((\omega,\tilde{p}_{\omega})\cup Y),R^{s(\omega)}((\omega,\tilde{p}_{\omega})\cup Y)$.
\end{enumerate}
\end{definition}

(CP1) says that there exists a vector of (low) prices at which firms
want to buy all their upstream trades; (CP2) says that there exists
a vector of (high) prices at which firms want to sell all their downstream
trades; (CP3) says whenever a seller rejects a contract for a trade
at a particular price and the buyer rejects a contract for the same
trade at a higher price, there exists a price (either $p_{\omega}$
or $p_{\omega}+1$) for the trade at which they both reject the contract
whenever the set of other offered contracts is unchanged. It is worth
highlighting that (CP3) would be innocuous if prices were continuous.

\begin{definition}\textit{Price Monotonicity} (PM): Consider an
outcome $A$ and two other contracts $\{x,x'\}\notin A$ for the same trade $\omega$ that differ only in price i.e. $x=(\omega,p_{\omega})$ and $x'=(\omega,p_{\omega}')$ such that $p_{\omega}>p_{\omega}'$.
If $f=b(x)=b(x')$, then $x\notin C^f(A\cup \{x,x'\})$, and
if $f=s(x)=s(x')$, then $x'\notin C^f(A\cup \{x,x'\})$.\end{definition}

This assumption says that all things being equal firms strictly prefer
to buy a cheaper upstream trade and to sell a more expensive downstream
trade. It extends the ``generalized salary condition'' \citep{Roth:85} or ``Pareto separability" \citep{Roth:84} used in the context of two-sided markets  in contract networks.

Our price-adjustment process mimics the one described
by \citet{KeCr:82} and \citet{Roth:84} except that now the sellers
are not bound by the agreed contracts.%
\footnote{The price-adjustment process is analogous with
buyers not being tied to contracts.%
} In fact, it is a special case of operator $\Phi$ applied
on a set of contracts used to prove Lemma \ref{main} but since we are able
to keep track of the prices of all trades and we can find supporting
competitive equilibrium prices once the process terminates and finds
a (fully) trail-stable allocation.
The intuition here is that prices of over-demanded trades increase.
Initially, every upstream trade is demanded by the buyers. Buyers
continue to raise prices of (upstream) trades until every demanded
(upstream) trade has a supplier or we can find a set of prices at
which neither party wants to trade. This is a (fully) trail-stable contract
allocation and from here we can construct competitive equilibrium
prices to support it.%
\footnote{\citet[Theorem 6]{HaKoNiOsWe:11} show that supporting competitive
equilibrium prices can also be found for any stable contract allocation
when utility functions are quasilinear. Their proof is rather different.%
} This gives us our final result.

\begin{theorem}\label{EquilibriumTheorem}Consider a set of contracts
$X$ that specifies trades and prices and assume that choice functions
of $F$ are fully substitutable, feasible and satisfy IRC. In addition, assume
that (CP) and (PM) are satisfied. Then a competitive equilibrium arrangement
exists and a competitive equilibrium outcome is (fully) trail-stable. \label{theorem:comp-eq}
\end{theorem}
\section{Conclusion}\label{concsec}
Set stability is an appealing stability concept, but in general contract networks set-stable outcomes may not exist and they are not computationally tractable. In this paper, we introduced a new natural stability notion for general contract networks, called trail stability. We showed that any contract network has a trail-stable outcome when
choice functions are fully substitutable. We then showed that outcomes satisfying an even stronger stability concept -- full trail stability -- always exist and have a natural lattice structure and inherit a host of properties studied in two-sided and supply-chain settings. Moreover, we described how set-stable outcomes, chain-stable and (fully) trail-stable outcomes are related in general networks. We then showed that in networked markets competitive equilibrium can exist without the quasilinear assumption on utility functions.
Full substitutability is crucial for existence of trail-stable outcomes since previous maximal
domain results for many-to-many matching markets apply in our case (see, for example, \citet[Theorem 6]{HaKo:12} and \citet[Theorem 2]{HaKo:11}).
When firms have quasilinear utility functions, (full) substitutability
is not necessary for competitive equilibrium and even when all agents
have complementary preferences competitive equilibrium may exist \citep{BaKl:13,Drex:13,HaKo:15,Teyt:14}.
Although \citet{AlTe:15} show that trail-stable outcomes exist in supply chains even in the presence of upstream complementarities with general choice functions, it is not clear whether this result can be extended to general contract networks. Finally, it would be interesting to understand how this model can be tested and estimated empirically. This is a fruitful area for future research.

\newpage

\section{Appendix}

\begin{proof}[Proof of Lemma \ref{ladlasirc}]
Consider $Y\subseteq X_f$ and $z\in X_f^B \setminus Y$ such that   $z\notin C^f(Y\cup\{z\})$. Then, from SSS, $C_B^f(Y\cup\{z\}) \subseteq C_B^f(Y) $ and from CSC  $C_S^f(Y\cup\{z\}) \supseteq C_S^f(Y)$. If choice functions satisfy LAD/LAS then
$|C_{B}^{f}(Y)|-|C_{S}^{f}(Y))|\leq|C_{B}^{f}(Y\cup\{z\})|-|C_{S}^{f}(Y\cup\{z\})|$
so there must be equality, so $C^f (Y\cup\{z\}) =C^f(Y)$.
\end{proof}

\subsection{Proof of Theorem \ref{grouphopeless}}

\begin{proof}[Proof of Theorem \ref{grouphopeless}]
Problem GS is clearly belongs to complexity class NP as verifying that $Z$ is a blocking set for $A$ requires a polynomial
time proof.

To show that GS is NP-hard we reduce the NP-complete partition problem to
GS. An instance of the partition problem is given by a $k$-tuple
$A=(a_1,a_2,\ldots,a_k)$ of positive integers such that $a_1\le a_2\le
\ldots\le a_k$ holds. The answer to this problem is
YES if and only if there is a subset $I$ of $\{1,2,\ldots,k\}$ such that
$\sum_{i\in I}a_i=s$ where $2s=\sum_{i=1}^ka_i$. So assume that the partition
problem is given by $\A=(a_1,a_2\ldots a_k)$. Construct a trading network
with firms $f$ and  $g$ and with contracts $y$ and $x_i$ such that $f=s(y)=b(x_i)$ and $g=b(y)=s(x_i)$ for
$i\in\{1,2,\ldots,k\}$. Define choice function $C_\A^f$ with the help of
$s:=\frac 12\sum_{i=1}^ka_i$ by
\[
C_\A^f(X|Y)=\left\{\begin{array}{rcl}
(X|Y)&\qquad\qquad&\mbox{if }\sum\{a_i:x_i\in X\}\ge s\\
(X|\emptyset)&&\mbox{if }\sum\{a_i:x_i\in X\}< s
\end{array}
\right.
\]
It is easy to check that $C_\A^f$ satisfies the full substitutability condition and
IRC. Define $C_\A^g$ as follows:
\[
C_\A^g(Y|X)=\left\{\begin{array}{rcl}
(\emptyset|\emptyset)&\qquad&\mbox{if } Y=\emptyset\\
(Y|X)&&\mbox{if }Y=\{y\}\mbox{ and }\sum\{a_i:x_i\in X\}\le s\\
(Y|X\cap\{x_1,x_2,\ldots,x_t\})&&\mbox{if }Y=\{y\}\mbox{ and
}\sum\{a_i:x_i\in X, i\le t\}\le s< \sum\{a_i:x_i\in X, i<t+1\}
\end{array}
\right.
\]
One can readily check that $C_\A^g$ also satisfies the full substitutability condition and
IRC. That is, based on the partition problem instance, we have
determined a trading network. To define our GS instance, define an outcome
$A=\emptyset$. We have to show that the answer to the partition problem is
YES if and only if $A=\emptyset$ is not set-stable.

Assume now that the answer to our partition
problem instance is YES, that is $\sum_{i\in I}a_i=s$. Define
$X_I:=\{x_i:i\in I\}$ and $Y=\{y\}$. By the above definitions,
$C_\A^f(X|Y)=(X|Y)$ and $C_\A^g(Y|X)=(Y|X)$, hence $X\cup Y$ blocks
$A=\emptyset$, so $A$ is not set-stable.

Assume now that $A=\emptyset$ is not set-stable. This means that there is
a blocking set $Z$ to $A$ and define $I=\{i:x_i\in Z\}$, $X_I:=\{x_i:x_i\in
Z\}$
and $Y:=Z\cap \{y\}$. As $Z$ is blocking, we have $C_\A^f(X_I|Y)=(X_I|Y)$ and
$C_\A^g(Y|X_I)=(Y|X_I)$. If $Y=\emptyset$ then
$(Y|X_I)=C_\A^g(Y|X_I)=C_\A^g(\emptyset|X_I)=(\emptyset,\emptyset)$, so
$Z=X_I\cup Y=\emptyset\cup\emptyset=\emptyset$, and hence $Z$ is not
blocking. Otherwise, $Y=\{y\}$, and from $C_\A^g(Y|X_I)=(Y|X_I)$ we get that
$\sum_{i\in I}a_i\le s$. Moreover, from $y\in C_\A^f(X_I,Y)$ we get that
$\sum_{i\in I}a_i\ge s$. Consequently $\sum_{i\in I}a_i= s$, and the answer
to the partition problem is YES.

To prove the second part of the theorem, define a contract network
with firms $f$ and  $g$ and with contracts $y$ and $x_i$ such that $f=s(y)=b(x_i)$ and $g=b(y)=s(x_i)$ for for $1\le i\le 2n$. Define the following choice function
\begin{equation}\label{cf}
C_0^f(X|Y)=\left\{\begin{array}{rcl}
(X|Y)&\qquad\qquad&\mbox{if }|X|\ge n+1\\
(X|\emptyset)&&\mbox{if }|X|\le n
\end{array}
\right.
\end{equation}
For $I\subseteq \{1,2,\ldots,n\}$ define $X_I:=\{x_i:i\in I\}$. For $|I|=n$ let
\[C_I^f(X|Y)=\left\{\begin{array}{rcl}
(X|Y)&\qquad\qquad&\mbox{if }|X|\ge n+1\mbox{ or if }X=X_I\\
(X|\emptyset)&&\mbox{if }|X|\le n\mbox{ and }X\ne X_I
\end{array}
\right.
\]
It is straightforward to check that choice functions $C^f_0$ and $C^f_I$
above satisfy the full substitutability condition and IRC.
Define the following choice function for $g$
\begin{equation}\label{cg}
C^g(Y|X)=\left\{\begin{array}{rcl}
(\emptyset|\emptyset)&\qquad&\mbox{if } Y=\emptyset\\
(Y|X)&&\mbox{if }Y=\{y\}\mbox{ and }|X|\le n\\
(Y|X\cap\{x_1,x_2,\ldots,x_t\})&&\mbox{if }Y=\{y\}\mbox{ and
}|\{x_i\in X: i\le t\}|= n
\end{array}
\right.
\end{equation}
As $C^g=C^g_\A$ for $\A=(1,1,\ldots,1)$, $C^g$ also satisfies the full substitutability condition and IRC.

Now assume that an instance of problem GS is given by the above network
and an outcome $A=\emptyset$. Assume that the choice functions are not given
explicitly, but by value-returning oracles. Moreover, we know exactly that
the choice function of $g$ is the one defined in \eqref{cg} and we know
that the choice function of $f$ is either $C^f_0$ or $C^f_I$ for some $I$.
It is easy to check that $A$ is not set-stable if and only if $C^f=C^f_I$ and
in this case the only blocking set is $Z=X_i\cup\{y\}$. So if one has to
decide set stability of $A$, then one must determine the $C^f(Z)$ values
for all such possible $Z$, and this means $\binom{2n}n$ oracle calls.
\end{proof}

\subsection{Proof of Lemma \ref{main}}

Consider $Y^{B}$ and $Z^{S}$, which are subsets of $X$, and represent
sets of available upstream and downstream contracts for all agents,
respectively. Define a lattice $L$ with the ground set $X\times X$
with an order $\sqsubseteq$ such that $(Y^{B},Z^{S})\sqsubseteq(Y'^{B},Z'^{S})$
if $Y^{B}\subseteq Y'^{B}$ and $Z^{S}\supseteq Z'^{S}$.

Furthermore, define a mapping $\Phi$ as follows:
\begin{eqnarray*}
\Phi_{B}(Y^{B},Z^{S}) & = & X\setminus R_{S}(Z^{S}|Y^{B})\\
\Phi_{S}(Y^{B},Z^{S}) & = & X\setminus R_{B}(Y^{B}|Z^{S})\\
\Phi(Y^{B},Z^{S}) & = & (\Phi_{B}(Y^{B},Z^{S}),\Phi_{S}(Y^{B},Z^{S}))
\end{eqnarray*}

where $R_{S}(Z^{S}|Y^{B})\equiv\bigcup_{f\in F}R_{S}^{f}(Z^{S}|Y^{B})$
and $R_{B}(Y^{B}|Z^{S})\equiv\bigcup_{f\in F}R_{B}^{f}(Y^{B}|Z^{S}) $.
Clearly, $\Phi$ is isotone \citep{Flei:03,Ostr:08,HaKo:12} on $L$.
We rely on the following well-known fixed point theorem of Tarski.

\begin{theorem}\citep
Tars:55}\label{Knaster-Tarski} Let
$L$ be a complete lattice and let $\Phi:L\rightarrow L$ be an isotone
mapping. Then the set of fixed points of $\Phi$ in $L$ is also a
complete lattice.\end{theorem}

\begin{proof}[Proof of Lemma \ref{main}]

Existence of fixed-points of $\Phi$ follows from Theorem \ref{Knaster-Tarski} since $(X\times X, \sqsubseteq)$ is a complete lattice.%
\footnote{Hence, we do not actually require the assumption of the finiteness
of contracts as long as lattice $L$ is appropriately defined. However,
we maintain this assumption for ease of comparison with previous results.%
}

We claim that every fixed point $(\dot X^{B},\dot X^{S})$ of $\Phi$
corresponds to an outcome $\dot X^{B}\cap \dot X^{S}=A$ that is {fully trail}-stable.
First, we show that $A$ is individually rational. Observe that if $(\dot X^{B},\dot X^{S})$ is a fixed point then $\dot X^S \cup \dot X^B=X$. To see this suppose for contradiction that there is a contract $x\notin \dot X^S \cup \dot X^B$. Then  $x \notin R_{S}(\dot X^{S}|\dot X^{B})$ therefore $x \in X\setminus R_{S}(\dot X^{S}|\dot X^{B})=\dot X^B$. So $x$ is has to be  in $ \dot X^S \cup\dot  X^B$
This implies that $ R_{S}(\dot X^{S}|\dot X^{B})=X\setminus \dot X^B=\dot X^S \setminus A$ so $C_{S}(\dot X^{S}|\dot X^{B})=A$ and similarly  $C_{B}(\dot X^{B}|\dot X^{S})=A$ From this, we can see that $A$ is individually rational.

Second, we show that $A$ is fully trail-stable. This is similar to
Step 1 of the Proof of Lemma 1 in \citet{Ostr:08}. Suppose that $T=\{x_{1},...x_{m}\}$
is a locally blocking trail and assume towards a contradiction that  $T\cap A=\emptyset$.
Since we have that $x_{1}\in C_{S}^{s(x_{1})}(A\cup x_{1}|A)$, we
must have that $x_{1}\in C_{S}^{s(x_{1})}(\dot X^{S}\cup x_{1}|A)$
Since if  $C_{S}^{s(x_{1})}(\dot X^{S}\cup x_{1}|A) \subseteq \dot X^S$ then by IRC $C_{S}^{s(x_{1})}(\dot X^{S}\cup x_{1}|A)=A$, therefore $ C_{S}^{s(x_{1})}(A\cup x_{1}|A)=A$
 Also, $x_{1}\in C_{S}^{s(x_{1})}(\dot X^{S}\cup x_{1}|\dot X^{B})$ (by
CSC). If $x_{1}\in \dot X^{S}$, then $x_{1}\in \dot X^{B}=X\setminus R_{S}(\dot X^{S}|\dot X^{B})$.
But we assumed that $x_{1}\notin A$, so $x_{1}\in\dot  X^{B}$.

Now, consider $x_{2}$. By definition of a locally blocking trail, we have that  $x_{2}\in C_{S}^{s(x_{2})}(A\cup x_{2}|A\cup x_{1})$.
Once again by full substitutability  and IRC, we obtain that
and $x_{2}\in C_{S}^{s(x_{2})}(\dot X^S\cup x_{2}|\dot X^B\cup x_{1})$.
If $x_{2}\in \dot X^S$, then $x_{2}\in \dot X^B=X\setminus R_{S}(\dot X^S|\dot X^B)$.
But we assumed that $x_{2}\notin A$, so $x_{2}\in \dot X^B$.
Now proceed by induction,
we show that every $x\in T$ is in $\dot X^B$. Consider the last contract $x_m$.
Since  $x_m \in C_B^{b(x_m)} (A\cup x_{m}|A)$, using the same argument we had for $x_1$, we get that $x_m\in \dot X^S$. A contradiction.\\
Now we show that every fully trail-stable outcome corresponds to a fixed point:\\
Suppose $A$ is fully trail-stable. \ch{For every $x_i \notin A$,
if there exists a trail $\{ x_1 x_2 \dots x_i \}$ such that
$x_{1}$ is $(A,s(x_{1}))$-rational, and
$\{x_{m-1}, x_{m}\}$ is $(A,f_m)$-rational for
$f_{m}=b(x_{m-1})=s(x_{m})$ whenever $1<m\le i$, then let $x_i \in X_0^B$, otherwise $x_i \in X_0^S$}.
Let $\dot X^B=A\cup X_0^B$ and $\dot X^S=A\cup X_0^S$.
Clearly $\dot X^S  \cup \dot X^B=X$.

Outcome $A$ is individually rational, so $C^f(A)=A_f$ for all $f \in F$.
For every firm $f$, if $f=s(x)$ and $x\in \dot X^S\setminus A$ then  $x \notin C^f(A \cup  \{x\}) $ otherwise $x$ would be in $X_B$. From SSS, $C^f_S(\dot X^S |A)=A$.
And if $f=b(y)$ and $y\in \dot X^B \setminus A$ then  $y \notin C^f(A \cup  \{y\}) $ otherwise the trail ending in $y$ would be a locally blocking trail.   From SSS, $C^f_B(\dot X^B |A)=A$. Moreover, $\{x, y\} \nsubseteq C(A \cup \{x,y\})$ otherwise $x$ would be in  $\dot X^B$.
These together imply that $C_S(\dot X^S |\dot X^B)=A$ and $C_B(\dot X^B |\dot X^S)=A$.
Therefore  $R_S(\dot X^S |\dot X^B)=\dot X^S \setminus A$, $R_B(\dot X^B |\dot X^S)=\dot X^B \setminus A$, so $X \setminus R_S(\dot X^S |\dot X^B)=\dot X^B$, $X \setminus R_B(\dot X^B |\dot X^S)=\dot X^S$. \end{proof}

\subsection{Proof of Propositions \ref{fully-vs-trail}, \ref{group-vs-trail} and Lemma \ref{path-path}}

The key to this is the following two useful lemmata. In the proofs, we will use the concept of a circuit, which is a closed trail.
\begin{definition}
A non-empty sequence of different contracts $Q=\{x_{1},\ldots,x_{M}\}$ is a
\textit{circuit} if
$b(x_{m})=s(x_{m+1})$ holds for all $m=1,\ldots,M-1$, and $b(x_M)=s(x_1)$.
\end{definition}
\begin{lemma}\label{ratpair} Let $F$ be the set of agents and $X$ be the set of contracts in a contract
network with fully substitutable choice functions that satisfy IRC. If $Y$ and $Z$ are disjoint
sets of contracts and $f$ is an agent such that $Z_f$ is
$(Y,f)$-rational
then for any contract $z$ of $Z^B_f$ one of the
following options hold: (1) $z$ is $(Y,f)$-rational or (2) there exists
some $z'\in Z^S_f$ such that $\{z,z'\}$ is a $(Y,f)$-rational
pair or (3) there are $z_1,z_2,\ldots,z_k\in Z_f^S$ such that both
   $\{z,z_1,z_2,\ldots ,z_k\}$ and $\{z_i\}$ (for $1\le i\le k$) are
  $(Y,f)$-rational. For $z\in Z_f^S$ an analogous statement holds.
\end{lemma}

\begin{proof}[Proof of Lemma \ref{ratpair}]

We can suppose without loss of generality that $z\in X^B_f$.
From the SSS property, it follows that $z \in C^f(Y_f \cup  Z_f^S\cup \{z\})$.

\ch{Assume that $C^f(Y_f  \cup  Z_f^S \cup \{z\}) \cap Z^S_f  = \emptyset$. Therefore, we have
 $C^f(Y_f  \cup  Z_f^S\cup \{z\}) \subseteq (Y_f  \cup \{z\})
\subseteq (Y_f   \cup  Z_f^S\cup \{z\})$, so from IRC
 $z \in C^f(Y_f \cup \{z\})$, so $z$ is $(Y,f)$-rational, we get option (1). }

So if $z$ is not $(Y,f)$-rational then there are some  contracts $\{z_1, z_2 \dots z_k\}= C^f(Y_f  \cup  Z_f^S \cup \{z\}) \cap  Z_f^S$.  If there exists an $z_i$ such that is $z_i$ is not $(Y,f)$-rational, then using SSS  again, we have $z_i \in C^f(Y_f \cup  \{z, z_i\}) $.

Suppose $z \notin C^f(Y_f \cup   \{z, z_i\})$, then $C^f(Y_f \cup  \{z, z_i\}) \subseteq (Y_f \cup \{z_i\}  )$, and from IRC we have $ C^f(Y_f \cup \{z,z_i\})= C^f(Y_f \cup \{z_i\} ) $.
But since $z_i$ is not $(Y,f)$-rational this is impossible,  therefore  $\{z, z_i\} \subseteq  C^f(Y_f \cup   \{z, z_i\})$, we achieved a $(Y,f)$-rational pair.

If all of $\{z_1, z_2 \dots z_k\} $ are  $(Y,f)$-rational, we get option (3).\end{proof}

A consequence of Lemma
\ref{ratpair} is that full trail stability is a stronger property than
trail stability.

Later we are going to need the following lemma.

\begin{lemma}\label{shortcut}
Let $F$ be the set of agents and $f$ be an agent in a contract network with
fully substitutable choice functions that satisfy IRC. Assume that $Y$ is acceptable and
$x_1,x_2,\ldots,x_k\in X^B_f$ and $z_1,z_2,\ldots,z_k\in X^S_f$ such that
$\{x_i,z_i\}$ is a $(Y,f)$-rational pair for any $1\le i\le k$ but
$\{x_1,x_2,\ldots,x_k,z_1,z_2,\ldots,z_k\}$ is not $(Y,f)$-rational. Then
$\{x_i,z_j\}$ is a $(Y,f)$-rational pair for some $i\ne j$.

The above statement remains true if one or both of the contracts $x_1$ and $z_k$ are
\textit{void}. \ch{When we say that $x_1$ is void, we mean that:
\begin{itemize}
\item $x_1$ is empty, so
\item the trail starts with $z_1$, and
\item instead of $(Y,f)$-rationality of pair $\{x_1,z_1\}$ we need $(Y,f)$-rationality of $z_1$ and $i\ne 1$ in the
conclusion. }
When we say that both $x_1$ and $z_k$ are void, we mean that there is $(Y,f)$-rational pair $\{x_i,z_j\}$,  $i\ne j$ such that $\{x_i,z_j\}  \neq \{x_k,z_1\}$.
\end{itemize}
\end{lemma}

\begin{proof}[Proof of Lemma \ref{shortcut}]

Suppose, for example, that $z_j \notin C^f(Y\cup \{x_1,x_2,\ldots,x_k,z_1,z_2,\ldots,z_k\})$  for some $j$ such that both $x_j$ and $z_j$ exist.
Then from CSC, $z_j \notin C^f(Y\cup \{x_j,z_1,z_2,\ldots,z_k\})$.
But $x_j \in C^f( Y \cup \{x_j z_j\})$ so from CSC $x_j \in C^f(Y\cup \{x_j,z_1,z_2,\ldots,z_k\})$.
 Since $x_j$ is not $(Y,f)$-rational, there is a $z_l \in C^f(Y\cup \{x_j,z_1,z_2,\ldots,z_k\})$ therefore  $\{x_j, z_l\}$ is $(Y,f)$-rational and $l \neq j$.

In the case that $x_1$ is void and $z_1 \notin C^f(Y\cup \{x_2,\ldots,x_k,z_1,z_2,\ldots,z_k\})$, from CSC, $z_1 \notin C^f(Y\cup \{z_1,z_2,\ldots,z_k\})$. This is impossible when $z_1$ is $(Y,f)$-rational but none of the other $z_j$ contracts are $(Y,f)$-rational.
Therefore if we have found $(Y,f)$-rational pair $\{x_i,z_j\}$, then at least one of  $x_i$ and $z_j$ was not $(Y,f)$-rational by itself. \end{proof}

\begin{proof}[Proof of Lemma \ref{path-path}]
\ch{
Consider a fully trail-stable outcome $A$.
Suppose that $A$ is not trail-stable, i.e. there exists a blocking trail $T=\{x_1, x_2 \dots x_M\}$ for it. Without the loss of generality, we may assume that (b)ii holds in Definition \ref{trailstable}. The other case when (b)i holds can be proved analogously.

We are going to find indices $1 \le i_1 < i_2 < i_3 \dots i_{l} \le k$ such that
\begin{itemize}
\item    $x_{i_1}$ is $(A,s(i_1))$-rational, and
\item $b(x_{i_{m-1}})=s(x_{i_{m}})=f_m$ and $\{x_{i_{m-1}}, x_{i_{m}}\}$ is a $(A,f_m)$-rational pair   for all $1<m\le l$, and
\item  $x_{i_{l}}$ is  $(A,b(i_l))$-rational.
\end{itemize}
So this subset of the trail forms a locally blocking trail $T'$.

In the blocking trail $T$, choose the last contract $x_i  \in T$ such that $x_i$ is $(A,s(x_i))$-rational. There is at least one contract like this, since $x_1$ is  $(A,s(x_1))$-rational by definition. Let $i_1:=i$.

Suppose we have already found $i_1 \dots i_{m}$  that satisfies our requirements.
If $x_{i_m}$ is  $(A,b(x_{i_m}))$-rational, we end the trail there, and let $l=m$.
Otherwise,  from the definition of blocking trails, for $f_{m+1}=b(x_{i_m})$, the ending subsequence
 $T_{f}^{\ge m}=\{x_{m},...,x_{M}\}\cap T_{f}$ is $(A,f_{m+1})$-rational.
Using Lemma \ref{ratpair},  there is a contract $x_{i_{m+1}} \in T_{f}^{\ge m} \cap X_f^S$ such that $i_{m+1}> i_m$ and  $\{x_{i_{m-1}}, x_{i_{m}}\}$ is a $(A,f_m)$-rational pair.

\iffalse
If this trail reaches firm $f$ multiple times, let
 $T^B_f=\{a_1 , a_2 \dots a_k \} $ and  $T^S_f=\{b_1 , b_2 \dots b_k \} $ where $a_i, b_i$ are two consecutive contracts in the trail.
In the notation above  some of contracts can be void,
if the trail starts at $f$ then $a_1$ is void, if the trail ends at $f$ then $b_k$ is void.

We will show that there exist some $1 \le i_1 \le i_2 <i_3 \le i_4 <i_5  \dots <  i_{2l-1}\le i_{2l} \le k$ such that
\begin{itemize}
\item  either $\{a_{i_1}, b_{i_2}\}$ or  $b_{i_2}$ is $(A,f)$-rational  and
\item $\{a_{i_{2r-1}}, b_{i_{2r}}\}$ is $(A,f)$-rational  \ch{ for all $1<r<l$ }and
\item either  $a_{i_{2l-1}}$  or $\{a_{i_{2l-1}}, b_{i_{2r}}\}$ is  $(A,f)$-rational.
\end{itemize}

In the blocking trail $T=\{x_1, x_2 \dots x_M\}$, choose the last contract $x_i  \in T$ such that $x_i$ is $(A,s(x_i))$-rational. There is at least one contract like this, since $x_1$ is  $(A,s(x_i))$-rational by definition.

If none of the contracts $\{b_1 , b_2 \dots b_k \}$ is $(A,f)$-rational, let $i_1=1, i_2=1$. From definition, $\{a_1, b_1\}$ is $(A,f)$ rational.
If some $b_i$ is $(A,f)$-rational, choose the last one in the trail, i.e. $b_i$ is $(A,f)$-rational but for any $j>i$, $b_j$ is not $(A,f)$-rational.  Then let $i_1=i$. \\
Suppose we have already found $i_1 \dots i_{r}$ \ch{ that satisfies our requirements.}
If $a_{i_r+1}$ is  $(A,f)$-rational, we end the trail there, \ch{and let $a_{i_l}=a_{i_r+1}$.} From the definition of blocking trails, $\{a_{i_r+1}, b_{i_r+1} \dots a_k, b_k \}$ is $(A,f)$-rational.
If $a_{i_r+1}$ is not  $(A,f)$-rational, using
 Lemma \ref{ratpair},  there is a $b_{i_{r+1}}$ such that $i_{r+1}\ge i_r+1$ and $\{a_{i_r+1},  b_{i_{r+1}}\}$ is $(A,f)$ rational.
\fi
This way, we constructed a  locally blocking trail, therefore $A$ is not fully trail-stable.\\
}

To show that every set-stable  outcome is fully trail-stable,
consider an  outcome $A$ which  is not fully trail-stable,
and  choose the shortest locally blocking trail $T$ for it.  For every firm involved in $T$, if $T_f \nsubseteq C^f(A\cup T_f)$, then  using  Lemma \ref{shortcut} there is a \ch{upstream-downstream contract-pair} $x_j\in T$ and $z_l\in T$ such that $j \neq l$ and $\{x_j, z_l\}$ is  $(A,f)$-rational. This way we get a shorter locally blocking trail or circuit. Since this was the shortest trail, it must be a circuit. Repeat finding shortcuts until we get a  circuit $Z$ such that $Z_f \subseteq C^f(A\cup Z_f)$ for every firm $f$, so this a blocking set. Since $T\cap A= \emptyset$ and $Z\subseteq T$, $Z\cap A= \emptyset$. \end{proof}

\begin{proof}[Proof of Proposition \ref{fully-vs-trail}]
Lemma \ref{path-path} implies that if outcome $A$ is fully trail-stable
then $A$ is also trail-stable. So assume that outcome $A$ is
trail-stable. If $A$ is not fully trail-stable then there is a locally
blocking trail $T$ to $A$. The separability property of the choice functions imply that $T$ is a blocking trail, contradicting the trail stability of $A$. So $A$ is fully trail-stable.
\end{proof}

\begin{proof}[Proof of Proposition \ref{group-vs-trail}]
Lemma \ref{path-path} implies that if outcome $A$ is set-stable then $A$ is also fully trail-stable.
Assume that outcome $A$ is fully trail-stable, but not set-stable, so it has a blocking set $Z$.

Case 1: For every $z \in Z$, contract $z$ is neither $(A, s(z))$-rational nor $(A, b(z))$-rational. Then using Lemma \ref{ratpair} we can find a circuit $Q=\{z_1, z_2, \dots z_k\} \subseteq Z$ such that
\iffalse
 $b(z_i)=s(z_{i+1})$ for every $i$ and $b(z_i)=s(z_{i+1})$
\fi
  $\{z_i, z_{i+1}\}$ is an $(A,b(z_i))$-rational pair for every $1 \le i \le k$ and $\{z_k, z_1\}$ is  an $(A, b(z_k))$-rational pair.
Since every $\{z_i, z_{i+1}\}$  an $(A,b(z_i))$-rational set by itself, as choice functions are simple, intensity function $w$ must strictly decrease along circuit $Q$, which is impossible.\\

Case 2: If some contracts $z \in Z$ are $A$-rational. Suppose that $z_1$ is $(A, s(z_1))$-rational. From Lemma \ref{ratpair} we can find  a trail  $\{z_2, z_3 \dots z_k\} \subseteq Z$ such that for every $z_i$, either $\{z_i, z_{i+1}\}$ is a $(A,b(z_i))$-rational pair, (therefore $w(z_i) > w(z_{i+1})$) or there are some $y_1 \dots y_l $ such that $b(y_j)=s(z_i)$ for all $1\le j\le l$ and $\{z_i, y_1 \dots y_l\}$ is $(A,b(z_i))$-rational. From the simplicity property there is a $y_j$ such that $w(z_i) > w(y_j)$, this $y_j$ contract will be $z_{i+1}$.
The trail terminates at the first occasion when $z_i$ is \ch{$(A,b(z_i))$-rational}.

 Since the intensity strictly decreases, we cannot get back to a contract used earlier in the trail, so the trail must terminate.
 \ch{Let us pick a contract $z_i$ in the trail such that it is the last one which is $(A,s(z_i))$-rational}, and then choose the smallest $j$ such that $j\ge i$ and $z_j$ is $(A,b(z_j))$-rational.
From Lemma \ref{ratpair}, the trail from $z_i$ to $z_j$ is locally blocking, so outcome $A$ is not fully trail-stable.
\end{proof}

\subsection{Proofs of Lemma \ref{weaker-lattice} and Lemma \ref{fully-stable-lattice}}

\subsubsection{The sublattice property of fixed points}

We can rephrase the definitions of the Laws of Aggregate Demand and Supply (LAD/LAS) in the following way:

If the choice functions of firm $f$ satisfy LAD/LAS, for sets of contracts  $Y' \subseteq Y \subseteq X^B_f$, and $Z \subseteq Z' \subseteq X^S_f$ (i.e. $(Y', Z') \sqsubseteq (Y,Z)$) then $|C_{B}^{f}(Y'|Z')|-|C_{S}^{f}(Z'|Y')|\leq|C_{B}^{f}(Y|Z)|-|C_{S}^{f}(Z|Y)|$.

For every firm $f$ we define a weight function on the contracts in $X_f$, namely let $w(x)=1$  if $x \in X^B_f$ and $w(x)=-1$ if $x \in X^S_f$. So $w(C^f(Y,Z))=|C_{B}^{f}(Y|Z)|-|C_{S}^{f}(Z|Y)|$.
Therefore if $C^f$ satisfies LAD/LAS, then $(Y', Z') \sqsubseteq (Y,Z)$ implies $w(C^f(Y', Z')) \le w(C^f (Y,Z))$.\\

Let $ Y$ and $Y'$ be subsets of $X^B_f$,  $Z$ and $Z'$ are subsets of  $X^S_f$.
We denote the complement of $Z$ in $X^S_f$ with $\overline{Z}=X^S_f\setminus Z$.
Define the operation $(Y, Z) \wsm (Y',Z')= (Y \setminus Y', \overline {Z' \setminus Z)}$.
\ch{For a given firm $f$,
we call a set function $R: 2^X_f \to 2^X_f$ } a \emph{w-contraction} if for every $(Y', Z') \sqsubseteq (Y,Z)$ pair,  $w(R(Y,Z) \wsm R(Y',Z')) \leq w((Y,Z) \wsm (Y',Z'))$

Let us describe some properties of this $\wsm$ operation:
\begin{lemma}\label{wsm}
For a firm $f$, let $ Y$ and $Y'$ be subsets of $X^B_f$,  $Z$ and $Z'$ are subsets of  $X^S_f$ such that  $(Y', Z') \sqsubseteq (Y,Z)$. Then the following holds:
\begin{enumerate}
\item
   $w((Y,Z) \wsm (Y',Z')) = w((Y,Z))-w((Y',Z'))-|X^S_f|$.
\item
For any $(A,B)$ pair, $w((A,B) \wsm (Y,Z)) \le w((A,B) \wsm (Y',Z'))$.
\item
If $(Y,Z) \sqsubseteq (A,B)$ then  the $w((A,B) \wsm (Y,Z)) = w((A,B) \wsm (Y',Z'))$ equality  implies $(Y', Z') = (Y,Z)$.
\end{enumerate}
\end{lemma}

\begin{proof}
Let us tackle each statement separately:
\begin{enumerate}
\item
$w((Y,Z) \wsm (Y',Z')) = |Y\setminus Y'|-|\overline{Z'\setminus Z}|=|Y|-|Y'|-|X^S_f|+|Z'|-|Z|= w((Y,Z))-w((Y',Z'))-|X^S_f|$.
\item
Since $Y \supseteq Y'$, this implies $A\setminus Y \subseteq A \setminus Y'$,
and similarly $Z \subseteq Z'$ gives us $Z\setminus B \subseteq Z' \setminus B$, so  $\overline{Z\setminus B} \supseteq \overline {Z'\setminus B}$, therefore $w((A,B) \wsm (Y,Z)) =|A\setminus Y|- |\overline{Z \setminus B}|\le |A\setminus Y'|- |\overline{Z' \setminus B}|=w((A,B) \wsm (Y',Z'))$
\item
If $w((A,B) \wsm (Y,Z)) = w((A,B) \wsm (Y',Z'))$ then equality must hold at $|A\setminus Y|= |A\setminus Y'|$ and
$|\overline{Z \setminus B}|=|\overline{Z' \setminus B}|$.
Since $Y' \subseteq Y \subseteq A$ and $Z' \supseteq Z \supseteq B$, we get that $Y=Y'$ and $Z=Z'$.
\end{enumerate} \end{proof}

\begin{lemma}\label{contraction}
For a given firm $f$, if the firm's choice functions are fully substitutable and satisfy LAD/LAS, then the rejection function $R^f$ is  $ \sqsubseteq$-isotone and a $w$-contraction.
\end{lemma}

\begin{proof}
Let $Y$ and  $Y'$ be subsets of $ X^B_f$ and $Z$ and $Z'$ are be of $ X^S_f$, and moreover let
$(Y', Z') \sqsubseteq (Y,Z)$.\\
We have seen earlier that $R^f$ is  $ \sqsubseteq$-isotone, so $R^f(Y', Z') \sqsubseteq  R^f(Y,Z)$.
To prove that it is $w$-contraction,
 $w(R^f(Y,Z) \wsm R^f(Y',Z'))+|X^S_f|=w(R^f(Y,Z)) -w( R^f(Y',Z'))= w((Y,Z) \setminus C^f(Y,Z))-w((Y', Z')\setminus C^f(Y',Z'))=w(Y,Z) -w(C^f(Y,Z))- w(Y',Z') +w( C^f(Y',Z')) \leq w(Y,Z) - w(Y',Z')=w((Y,Z) \wsm (Y', Z'))+|X^S_f|$. We used that $w(C^f(Y', Z')) \le w(C^f (Y,Z))$.
If we subtract $|X^S_f|$ from both sides, we get that\\ $w(R^f(Y,Z) \wsm R^f(Y',Z'))\leq w((Y,Z) \wsm (Y', Z'))$, so $R^f$ is indeed a $w$-contraction.
\end{proof}

We will work on the $(2^{(X,X)} , \wcup, \wcap)$ lattice. We can imagine it as a network that contains exactly two (unrelated) copies of each contract, \ch{one for the buyer and one for the seller of the contract.}

Now the $C^f$ choice functions of the firms are defined over  disjoint set of contracts, so for every $Y \subseteq (X,X)$ we can define $C(Y)= \bigcup_{f\in F} C^f(Y_f) $. Similarly  $R(Y)= \bigcup_{f\in F} R^f(Y_f) $.
\ch{On this whole network,
we call a set function $R: 2^{(X,X)} \to 2^{(X,X)}$  a \emph{w-contraction} if for every firm $f$ the corresponding $R_f$ was a $w$-contraction. }

Let us denote the set of the starting half-contracts (seller's side) with $X^S_F= \bigcup_{f \in F} X^S_f$, and the set of ending half-contracts (buyer's side) with $X^B_F= \bigcup_{f \in F} X^B_f$. Now
 $|X^S_F|=|X^B_F|=|X|$.

Let $Y \subseteq X^B_F$ and  $Z \subseteq X^S_F$.
 The \emph{dual} of $(Y,Z)$  is what we get by switching the two parts.  We denote it with $(Y,Z)^*=(Z,Y)$.

In this model let all the contracts in $X^S_F$ have weight $w=-1$ and all contracts in $X^B_F$ have weight $w=1$.

\begin{lemma}\label{sublat}
If $F: 2^{(X,X)} \to 2^{(X,X)}$ is $\sqsubseteq$-isotone and a $w$-contraction then fixed points of $F$ form a nonempty sublattice of $(2^{(X,X)}, \widetilde \cup, \widetilde \cap)$
\end{lemma}

\begin{proof}
By Tarski's fixed-point theorem, the set of fixed points is nonempty. Now let $U \subseteq (X,X)$ and $V\subseteq (X,X) $.  Assume that $F(U)=U$ and $F(V)=V$. By monotonicity, $U\wcap V=F(U) \wcap F(V)  \sqsupseteq F(U\wcap V)$ and $U\wcup V=F(U) \wcup F(V) \sqsubseteq F(U\wcap V)$.
From the $w$-contraction property and Lemma \ref{wsm}
\[w(U\wsm (U\wcap V)) \ge w(F(U)\wsm F(U\wcap V)) \ge w(U\wsm (U\wcap V))\]
\[w((U\wcup V)\wsm U) \ge w(F(U \wcup V)\wsm F(U)) \ge w((U\wcup V) \wsm U)\]
hence there must be equality throughout.
Using the third part of Lemma \ref{wsm} we can see that  $(U\wcap V) =  F(U\wcap V)$ and  $(U\wcup V) =  F(U\wcup V)$ so they are also fixed points of $F$.
\end{proof}

\begin{obs}\label{star}
Consider two sets of contracts $(Y,Z)$ and  $(Y',Z')$ , where $Y, Y' \subseteq X^B_F$ and  $Z, Z' \subseteq X^S_F$ and
$(X,X)\setminus (Y,Z) =(X\setminus Y, X \setminus Z)$.
If $(Y', Z') \sqsubseteq (Y,Z)$, then
$((X\setminus Y, X \setminus Z)^* \wsm (X\setminus Y', X \setminus Z')^*)=((X\setminus Z)\setminus (X\setminus Z'), \overline {(X\setminus Y')\setminus (X\setminus Y)})=((Z' \setminus Z), \overline {(Y \setminus Y')})=((X,X)\setminus ((Y,Z) \wsm (Y',Z'))^*$
\end{obs}

\begin{theorem}
If the choice functions of all agents are fully substitutable and satisfy LAD/LAS, then the fixed points of
$\Phi(Y,Z) = ( X\setminus R_{S}(Z|Y), X\setminus R_{B}(Y|Z))$ form a nonempty, complete sublattice of $(2^X \times 2^X, \widetilde \cup, \widetilde \cap)$.
\end{theorem}

\begin{proof}

The $\Phi(Y,Z) = ( X\setminus R_S(Z|Y), X\setminus R_B(Y|Z))$ function can be also written as  $\Phi (Y)=((X,X) \setminus R(Y,Z))^*$. Since $R$ is $\sqsubseteq$-isotone,    $\Phi$ is also $\sqsubseteq$-isotone.  We need to show that $\Phi$ is a $w$-contraction. Suppose that $(Y',Z')  \sqsubseteq (Y,Z)$. Using Observation \ref{star}, $w(\Phi (Y,Z) \wsm \Phi (Y',Z'))=w(((X,X) \setminus R(Y,Z))^* \wsm ((X,X) \setminus R(Y',Z'))^*) = w(((X,X)\setminus (R (Y,Z) \wsm R (Y',Z')))^*)= w(R (Y,Z) \wsm R (Y',Z')) \le w( (Y,Z) \wsm  (Y',Z'))$ because in  Lemma \ref{contraction} we showed that $R$ is a $w$-contraction.

Since $\Phi$ is  $\sqsubseteq$-isotone and a $w$-contraction,  Lemma \ref{sublat} gives that the fixed points of $\Phi$ form a sublattice of $(2^{(X,X)}, \widetilde \cup, \widetilde \cap)$.
\end{proof}

\subsubsection{Lattice for the terminal agents}

\begin{lemma}\label{PI}
If choice function $C:2^X\to 2^X$
is same-side substitutable and satisfies IRC then  $C(Y\cup Z)=C(Y\cup C(Z))$ holds for any
  subsets $Y,Z$ of $X$.
\end{lemma}
\begin{proof}
Since $C$ is same-side substitutable, $C(Y\cup Z) \subseteq (Y\cup C(Z))$. Using IRC we have that
$C(Y\cup Z) \subseteq (Y\cup C(Z)) \subseteq (Y \cup Z)$ implies that $C(Y\cup Z)=C(Y\cup C(Z))$.
\end{proof}

\begin{lemma}\label{partialorder}
For a set of contracts $X$, if choice functions of $F$ are fully substitutable and satisfy IRC, then terminal superiority is a partial order on \ch{terminal-fully-trail-stable} outcomes.
\end{lemma}

\begin{proof}[Proof of Lemma \ref{partialorder}]
We need to prove that $\preceq^S$ is reflexive, antisymmetric and
transitive. Assume that $A,A'$ and $A''$ are acceptable outcomes. As
$C^f(A_f\cup A_f)=C^f(A_f)=A_f$ holds for each agent (and hence for each terminal seller)
$f$, relation $\preceq^S$ is reflexive. If $A\preceq^SA'\preceq^SA$ then we
have $A_f=C^f(A_f\cup A'_f)=A'_f$ holds for any terminal agent $f$, hence
$A=A'$ and $\preceq^S$ is antisymmetric. For transitivity, assume that
$A\succeq^SA'\succeq^SA''$. Using this and Lemma \ref{PI}, we get for any
terminal agent $f$ that
\[
C^f(A_f\cup A''_f)=C^f(C^f(A_f\cup A'_f)\cup A''_f)=C^f(A_f\cup A'_f\cup
A''_f)=C^f( A_f\cup C^f(A'_f\cup A''_f))=C^f( A_f\cup A'_f)=A_f\ ,
\]
hence $A\succeq^S A''$ holds, indeed. This completes the proof.
\end{proof}

\begin{theorem}\label{terminallattice}
If $L$ is a nonempty complete sublattice of  $(2^X \times 2^X, \widetilde \cup, \widetilde \cap)$ then
$L_\mathcal{T}=\{(Y_\mathcal{T}, Z_\mathcal{T}): (Y, Z) \in L\}$ is a sublattice of  $(2^\mathcal{T} \times 2^\mathcal{T}, \widetilde \cup, \widetilde \cap)$.
\end{theorem}

\begin{proof}
For a given $(A_\mathcal{T}, B_\mathcal{T})$ there can be more than one inverse image in the original lattice.
\info{Let $(A^*, B^*)= \widetilde  \bigcup \{(Y, Z) \in L: (Y_\mathcal{T}, Z_\mathcal{T}) \sqsubseteq (A_\mathcal{T}, B_\mathcal{T}) \}  $} since $L$ is a complete lattice with lattice operations $ \widetilde \cup, \widetilde \cap$, this \ch{ $(A^*, B^*) \in L$ } and $(A^*_\mathcal{T}, B^*_\mathcal{T})=  (A_\mathcal{T}, B_\mathcal{T}) $. We call it the \textit{canonical inverse image} of  $(A_\mathcal{T}, B_\mathcal{T})$, since this is the $\sqsubseteq$-greatest among all inverse images.

If $(A_\mathcal{T}, B_\mathcal{T})$ and $(C_\mathcal{T}, D_\mathcal{T}) \in L_\mathcal{T}$, let us consider $(Y,Z)= (A^*, B^*) \wcap (C^*, D^*)$.
Since  $(Y,Z)\sqsubseteq  (A^*, B^*) $ this implies $(Y_\mathcal{T},Z_\mathcal{T})\sqsubseteq (A^*_\mathcal{T}, B^*_\mathcal{T})=(A_\mathcal{T}, B_\mathcal{T})$. Similarly $(Y_\mathcal{T},Z_\mathcal{T})\sqsubseteq (C_\mathcal{T}, D_\mathcal{T})$. We want to show that $(Y_\mathcal{T},Z_\mathcal{T})$ is the greatest lower bound of  $(A_\mathcal{T}, B_\mathcal{T})$ and $(C_\mathcal{T}, D_\mathcal{T}) $ in $ L_\mathcal{T}$.
We can see that $(Y^*, Z^* ) \sqsubseteq  (A^*, B^*) $ and $(Y^*, Z^* ) \sqsubseteq  (C^*, D^*) $ because $(A^*, B^*)$ is defined by the union of a greater set. Therefore $(Y^*, Z^* )=(Y, Z )$.

Suppose there exists a $(E_\mathcal{T},F_\mathcal{T}) \in  L_\mathcal{T}$ such that $(E_\mathcal{T},F_\mathcal{T}) \sqsubseteq (A_\mathcal{T},B_\mathcal{T})$ and  $(E_\mathcal{T},F_\mathcal{T}) \sqsubseteq (C_\mathcal{T},D_\mathcal{T})$ but $(E_\mathcal{T},F_\mathcal{T})$
\ch{$ \not \sqsubseteq$}
 $ (Y_\mathcal{T},Z_\mathcal{T})$.
Then in the original lattice  $(E^*,F^*) \sqsubseteq (A^*,B^*)$ and  $(E^*,F^*) \sqsubseteq (C^*,D^* )$ but $(E^*,F^*) $
\ch{$\not \sqsubseteq$}
  $(Y^*,Z^*)$. But this is impossible since  $(Y,Z)= (A^*, B^*) \wcap (C^*, D^*)$.
So we have found a unique greatest common lower bound of  $(A_\mathcal{T}, B_\mathcal{T})$ and $(C_\mathcal{T}, D_\mathcal{T})$.

\ch{
Similar argument can be made in order to find the lowest common upper bound of $(A_\mathcal{T}, B_\mathcal{T})$ and $(C_\mathcal{T}, D_\mathcal{T})$.
Let $(Y,Z)= (A^*, B^*) \wcup (C^*, D^*)$.
Since  $(Y,Z)\sqsupseteq  (A^*, B^*) $ this implies $(Y_\mathcal{T},Z_\mathcal{T})\sqsupseteq (A^*_\mathcal{T}, B^*_\mathcal{T})=(A_\mathcal{T}, B_\mathcal{T})$. Similarly $(Y_\mathcal{T},Z_\mathcal{T})\sqsupseteq (C_\mathcal{T}, D_\mathcal{T})$.

Suppose there exists a $(E_\mathcal{T},F_\mathcal{T}) \in  L_\mathcal{T}$ such that $(E_\mathcal{T},F_\mathcal{T}) \sqsupseteq (A_\mathcal{T},B_\mathcal{T})$ and  $(E_\mathcal{T},F_\mathcal{T}) \sqsupseteq (C_\mathcal{T},D_\mathcal{T})$ but $(E_\mathcal{T},F_\mathcal{T})$
\ch{$ \not \sqsupseteq$}
 $ (Y_\mathcal{T},Z_\mathcal{T})$.
Then in the original lattice  $(E^*,F^*) \sqsupseteq (A^*,B^*)$ and  $(E^*,F^*) \sqsupseteq (C^*,D^* )$ therefore $(E^*,F^*) \sqsupseteq (Y,Z)$, so  $(E^*_\mathcal{T},F^*_\mathcal{T})=(E_\mathcal{T},F_\mathcal{T}) \sqsupseteq (Y_\mathcal{T},Z_\mathcal{T})$, which is a contradiction.

So we have found a unique lowest common upper bound  of  $(A_\mathcal{T}, B_\mathcal{T})$ and $(C_\mathcal{T}, D_\mathcal{T})$, so  $(L_\mathcal{T}, \widetilde \cup, \widetilde \cap)$ is indeed a lattice. }\end{proof}

Now we consider only the contracts sold by the terminal sellers.
For any \ch{ $Y \subseteq X$, let  $Y_\mathcal{S}=\{x \in Y|s(x)\in \mathcal{T}$$\}$. }

Given two fully trail-stable outcomes $A$ and $A'$, let us denote the canonical stable pair \ch{(defined as at the end of Proof of Lemma \ref{main}) for $A$ with $\dot X^B$ and $\dot X^S$, and the canonical stable pair for $A'$ with $\dot X'^B$ and $\dot X'^S$.}
\ch{
\begin{lemma}\label{terminalorder} Given two fully trail-stable outcomes $A$ and $A'$, $C^f(A_f\cup A'_f)=A_f$
for each teminal seller if and only if $\dot X^S_\mathcal{S} \supseteq \dot X'^S_\mathcal{S}$ and
$\dot X^B_\mathcal{S} \subseteq \dot X'^B_\mathcal{S}$ holds. A similar statement holds for terminal
buyers.

\end{lemma}
\begin{proof}
If $f$ is a terminal seller, $C^f(\dot X^S)=A_f$ and
$C^f(\dot X'^S)=A'_f$. Suppose that $\dot X^S_{\mathcal S} \supseteq \dot X'^S_{\mathcal S}$.  By IRC, $A_f \subseteq A_f\cup A'_f \subseteq \dot X^S_f$ implies that
$C^f(A_f\cup A'_f)=A_f$.

For the opposite direction, take a contract $x \in  X_f$ such that $x \notin
C^f(A'_f \cup x)$.  We use Lemma \ref{partialorder}, $A \succeq^S A'
\succeq^S x$, therefore $A \succeq^S x$, so $x \notin C^f(A_f \cup
x)$. When we define the stable pairs for $A$ and $A'$, if $x \in C^f(A'_f
\cup x)$ then $x\in \dot X^B$, if $x \notin C^f(A'_f \cup x)$ then $x\in
\dot X^S$. From the previous observation we can see that $\dot X^S_{\mathcal S} \supseteq
\dot X'^S_{\mathcal S}$ and $\dot X^B_{\mathcal S} \subseteq \dot X'^B_{\mathcal S}$.
The proof for terminal buyers is analogous.
\end{proof}
}

\begin{proof}[Proof of Lemma \ref{weaker-lattice}]
In the proof of Lemma \ref{main} we have seen that any fixed point
$(\dot X^B,\dot X^S)$ of isotone mapping $\Phi$ on lattice $L$ determines a fully-trail-stable
outcome $A^X$. Moreover, each stable outcome $A$ corresponds to at least
one fixed point $(\dot X^B,\dot X^S)$ of $\Phi$. From Theorem \ref{Knaster-Tarski},
it follows that fixed points of $\Phi$ form a lattice, hence there is a
$\sqsubseteq$-minimal fixed point $(\dot Y^B,\dot Y^S)$ and a $\sqsubseteq$-maximal one
$(\dot Z^B,\dot Z^S)$. We show that fully-trail-stable outcome $A^Y$ is seller-optimal and $A^Z$
is buyer-optimal.
So assume that $A=A^X$ is a fully-trail-stable outcome. As $(\dot Y^B,\dot Y^S)\sqsubseteq
(\dot X^B,\dot X^S)\sqsubseteq (\dot Z^B,\dot Z^S)$, we have $\dot Y^B\subseteq \dot X^B\subseteq \dot Z^B$ and
$\dot Y^S\supseteq \dot X^S\supseteq \dot Z^S$. Lemma \ref{terminalorder} implies that
$C^f(A_f\cup A_f^Y)=A_f^Y$ and $C^f(A_f\cup A_f^Z)=A_f$ for any terminal
seller $f$ and $C_g(A_g\cup A_g^Y)=A_g$ and $C_g(A_g\cup A_g^Z)=A_g^Z$ for
any terminal buyer $g$. So, by definition $A$ is seller-superior to $A^Y$
and $A^Z$ is seller-superior to $A$.
\end{proof}

\begin{proof}[Proof of Lemma \ref{fully-stable-lattice}]
In the proof of Lemma \ref{main} we have seen that $A$ is fully
trail-stable if and only if there is canonical pair $(\dot X^B,\dot X^S)$ of
 such that $(\dot X^B,\dot X^S)$ is a fixed point of
isotone mapping $\Phi$ and $A=\dot X^B\cap \dot X^S$. Moreover, \ch{if the choice functions satisfy LAD/LAS, then fixed points of
$\Phi$ form a sublattice $L$ of $(2^X \times 2^X, \widetilde \cup, \widetilde \cap)$.
From Lemma \ref{terminallattice}, the projection of the above lattice to the terminals, $L_\mathcal{T}$ is also a lattice under $\sqsubseteq$
 and from Lemma \ref{terminalorder} this partial order coincides with $\preceq^S $.
Therefore, the fully trail-stable outcomes form a lattice under terminal-superiority. }
\end{proof}

\subsection{Proofs of Propositions \ref{ostrovsky} and \ref{vacancy}}

Our proof is similar to Ostrovsky's proof. \ch{First we investigate the restabilized outcome from $A$, which we play part in the proofs of both  Propositions \ref{ostrovsky} and \ref{vacancy}.
Let $A$ be an arbitrary fully trail-stable outcome in the original network, with a correspondong canonical pair  $(\dot X^B,\dot  X^S)$.}
After the new terminal seller $f'$ arrives, let $X$ be the set of all contracts in the new network, and let us define $(X^{*B},X^{*S})=(\dot X^B,\dot X^S\cup X_{f'})$.
 In the following, we will use $\Phi $
according to the choice fuctions on the new network, \ch{so $(\dot X^B,\dot X^S)$   does not need to be a fixed point of $\Phi$ anymore.}

 Since $X_{f'}\cap X^{*B} =\emptyset$,
for every firm $f\neq f'$,
$R_S^{f}(X^{*S}|X^{*B})=R_S^{f}(\dot X^{S}|\dot X^{B}) $ and
$R_B^{f}(X^{*B}|X^{*S})=R_B^{f}(\dot X^{B}|\dot X^{S})$.
For example, if $f$ has a conctracts with $f'$, contract $x=f'f$ was not offered for firm $f$ in $X^{*B}$ so it does not get rejected.

For firm $f'$, $R_S^{f'}(X^{*S}|X^{*B})=X_{f'} \setminus C_S^{f'}(X_{f'} )$ and
$R_B^{f'}(X^{*B}|X^{*S})=\emptyset$.

Therefore $\Phi(X^{*B},X^{*S})=(\dot X^B \cup C^{f'}(X_{f'}) ,\dot X^S\cup X_{f'})$.

So $(X^{*B},X^{*S})\sqsubseteq \Phi(X^{*B},X^{*S})$, and $\Phi$ is $\sqsubseteq$-isotone, so $ \Phi(X^{*B},X^{*S}) \sqsubseteq \Phi( \Phi(X^{*B},X^{*S}))$ and so on. The lattice of all possible subset-pairs is finite, so there is a $k$ such that $\Phi^k(X^{*B},X^{*S})=(\hat X^B, \hat X^S)$ is a fixed point.
So $(X^{*B},X^{*S})\sqsubseteq \Phi(X^{*B},X^{*S}) \sqsubseteq\Phi^k(X^{*B},X^{*S})=(\hat X^B, \hat X^S)$.
 Outcome $\hat A=\hat X^{B}\cap \hat X^{S}$ is fully trail-stable, and this is what we call the \textit{restabilized outcome} from $A$.

\begin{proof}[Proof of Proposition \ref{ostrovsky}]
If $f'$ is a terminal seller, and we start from outcome $A_{max}$ and  the $\sqsubseteq$-maximal pair  $(\dot Z^B, \dot  Z^S)$.
Using the previous method,
outcome $\hat A=\hat Z^{B}\cap \hat Z^{S}$ is the restabilized outcome from $A$.
In the new network there exists a  $\sqsubseteq$-maximal fixed point of $\Phi$, namely $(Z'^{B},Z'^{S})$, therefore
$(\dot Z^B,\dot Z^S\cup X_{f'})=(Z^{*B},Z^{*S})\sqsubseteq (\hat Z^B, \hat Z^S)\sqsubseteq (Z'^{B},Z'^{S})$.
The fully trail-stable outcome corresponding to the maximal fixed point is $A'_{max}=Z'^{B}\cap Z'^{S}$.
We have to show that $ A'_{max} $ is better for terminal buyers and worse for terminal sellers than the original $ A_{max}$.
If $f$ is a terminal buyer, since $(Z'^{B},Z'^{S})$ is fixed point of $\Phi$ and  $(\dot Z^{B},\dot Z^{S})$ was  fixed before the new agent arrived,  $C^f(Z'^{B})=A'_{f,max}$ and $C^f(Z^{*B})=A_{f,max}$ and  $Z^{*B}\subseteq Z'^{B}$ so from $C^f(Z'^{B}) \subseteq (A_{f,max} \cup A'_{f,max}) \subseteq Z'^{B}$ by IRC we obtain $C^f(A_{f,max} \cup A'_{f,max})=A'_{f,max}$ so $ A'_{f,max}$ is preferred by terminal buyers.

Similarly, if $f$ is a terminal seller outside $f'$,
  $C^f(Z'^{S})=A'_{f,max}$ and $C^f(Z^{*S})=A_{f,max}$ and  $Z'^{S}\subseteq Z^{*S}$ so from $C^f(Z^{*S}) \subseteq (A_{f,max} \cup A'_{f,max}) \subseteq Z^{*S}$ by IRC we obtain $C^f(A_{f,max} \cup A'_{f,max})=A_{f,max}$ so $ A_{f,max}$ is preferred by terminal buyers.

If $f' $ is a terminal buyer then we can use the same proof with reversing the roles of buyers and sellers.  \end{proof}
\begin{proof}[Proof of Proposition \ref{vacancy}]
If $f'$ is a terminal seller, and
$A$ is any fully trail-stable outcome in the original network, with canonical pair  $(\dot X^B,\dot  X^S)$, then
$(X^{*B},X^{*S})=(\dot X^B,\dot X^S\cup X_{f'}) \sqsubseteq (\hat X^B, \hat X^S)$. The restabilized outcome is $\hat A=\hat X^{B}\cap \hat X^{S}$, and similarly to the proof of  Proposition \ref{ostrovsky} one can show that initial producers
weakly prefer $A$ to $ \hat A$ and all end consumers  (other than $f'$) prefer $\hat A$ to $A$.\\
If $f'$ is a terminal buyer,  preferences are the opposite. \end{proof}

\subsection{Proof of Theorem \ref{EquilibriumTheorem}}

First three lemmata adapt construction of a stable outcome in the two-sided many-to-many market with contracts and prices by \citet{Roth:84}. We take the perspective of buyers i.e. buying firms are offering their upstream trades to corresponding sellers.
\begin{lemma}
\label{lemma:Prices-are-specified}
Prices are specified for each trade at every step.
\end{lemma}

\begin{proof}

Using (CP1), (CP2) and (PM), we know that all firms offer all their
upstream trades at prices $\hat{p}$ at step 1. Hence, prices are
$\hat{p}$ and every trade has a price at step 1. In the subsequent
steps $t>1$, since choice functions are feasible, any firm will choose
at most one trade at a given price. One of three situations may occur
to any trade $\omega$.
\begin{enumerate}
\item If a trade $\omega$ is offered at $p_{\omega}^{*}=p_{\omega}(t)$
and rejected by $s(\omega)$, its price is fixed at $p_{\omega}^{*}$
until it is offered again.
\item If a trade $\omega$ is offered at $p_{\omega}^{**}=p_{\omega}(t)$
and not rejected by $s(\omega)$, its price is fixed at $p_{\omega}^{**}$
(until the seller breaks the contract).
\item If a trade $\omega$ is not offered, its price remains at the level
$p_{\omega}^{*}$ when it was last offered and rejected.
\end{enumerate}
In every step, we have specified what the price of every trade is,
which completes the proof.  \end{proof}

\begin{lemma}Prices of all trades are not decreasing in every round.\label{lemma:Prices-of-increasing}\end{lemma}

\begin{proof}

This follows from (PM). Since firms offer their most preferred upstream
trades, a firm would never offer an upstream trade $(\omega,p_{\omega}+1)$
if $(\omega,p_{\omega})$ had not been rejected.
\end{proof}

\begin{lemma}Offers remain open. If a seller accepts a trade at round
$t$, the buyer will offer it at all subsequent rounds.\label{lemma:Offers-remain-open}\end{lemma}

\begin{proof}

Firms (as buyers) are not worse off from this since:
\begin{enumerate}
\item Choice functions satisfy SSS. Prices of other upstream trades are increasing
(Lemma \ref{lemma:Prices-of-increasing}) leaving a smaller offer
set of upstream contracts (use (PM)), which means that any chosen upstream
trade continues to be chosen.
\item Choice functions satisfy CSC. Prices of downstream trades are increasing
(Lemma \ref{lemma:Prices-of-increasing}) leaving a larger offer set
of upstream contracts (use (PM)), which means that any chosen upstream
trade continues to be chosen.
\end{enumerate} \end{proof}

\begin{lemma}Rejections remain final. If a seller rejects a trade
at round $t$, he will reject it at all subsequent rounds.\label{lemma:Rejections-remain-final.}\end{lemma}

\begin{proof}

Firms (as sellers) are not worse off from this since:
\begin{enumerate}
\item Choice functions satisfy SSS. Prices of other downstream trades are increasing
(Lemma \ref{lemma:Prices-of-increasing}) leaving a smaller offer
set of downstream contracts (use (PM)), which means that any rejected
downstream trade continues to be rejected.
\item Choice functions satisfy CSC. Prices of upstream trades are increasing
(Lemma \ref{lemma:Prices-of-increasing}) leaving a larger offer set
of downstream contracts (use (PM)), which means that any rejected downstream
trade continues to be rejected.
\end{enumerate} \end{proof}

\begin{proof}[Proof of Theorem \ref{theorem:comp-eq}]

When the algorithm terminates (by Tarski fixed-point theorem, it must),
we are at a (fully) trail-stable outcome $A$ (by Theorem
\ref{theorem:on-odd-cycle-contracts}).

We tracked a price for every trade (by Lemma \ref{lemma:Prices-are-specified}).
For trades $\Psi=\tau(A)$ that are realized at the trail-stable outcome
$A$, we assign prices specified in $A$ to those trades. Clearly,
these trades are chosen at these prices since the corresponding contracts
are chosen. If $\tau(A)=\Omega$, this indeed a competitive equilibrium.

If a trade $\omega$ has not been realized, then it must have not
been in $b(\omega)$'s chosen set in the final round $T$ (otherwise
both buyer and seller would choose the trade at price $\check{p}_{\omega}$).
That means it was rejected by $s(\omega)$ in some round $t<T$ at
a lower price $p_{\omega}^{*}$ and this price has not changed (by
(CP1), (PM), Lemma \ref{lemma:Prices-are-specified} and Lemma \ref{lemma:Prices-of-increasing}).
Since prices of other trades have increased (Lemma \ref{lemma:Prices-are-specified})
and using Lemma \ref{lemma:Rejections-remain-final.}, $s(\omega)$
will continue rejecting this trade at $p_{\omega}^{*}$ at $T$. Using
(CP3), we can find a price $\tilde{p}_{\omega}$ for every unrealized
trade one by one such that the trade is rejected by $b(\omega)$ and
$s(\omega)$. Assign some price $\tilde{p}_{\omega}$ to all such
trades. Note that this does not affect the choice of other contracts
(since prices are adjusted weakly downward for buyer and weakly upward
for the seller and they continue to reject the particular trade; adding
rejected trades is irrelevant to choices). Now all trades have been
assigned prices giving us a set of contracts $\kappa([\Omega^{*},p^{*}])$
where $p_{\omega}^{*}=p_{\omega}$ for $ $$(\omega,p_{\omega})\in A$
and $\tilde{p}$ otherwise. At these prices agents only choose contracts
they were allocated at $A$; the realized trades $\Psi$. Hence, this
is a competitive equilibrium and (full) trail stability is preserved. This
completes the proof. \end{proof}
\newpage
\singlespacing

\bibliographystyle{chicago}
\small