Chain stability in trading networks

Hatfield, John William; Kominers, Scott Duke; Nichifor, Alexandru; Ostrovsky, Michael; Westkamp, Alexander Article Chain stability in trading networks Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Hatfield, John William; Kominers, Scott Duke; Nichifor, Alexandru; Ostrovsky, Michael; Westkamp, Alexander (2021) : Chain stability in trading networks, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 16, Iss. 1, pp. 197-234, https://doi.org/10.3982/TE3839 This Version is available at: https://hdl.handle.net/10419/253496 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 16 (2021), 197–234 1555-7561/20210197 Chain stability in trading networks John William Hatfield McCombs School of Business, University of Texas at Austin Scott Duke Kominers Entrepreneurial Management Unit, Harvard Business School, Department of Economics and Center of Mathematical Sciences and Applications, Harvard University, and National Bureau of Economic Research Alexandru Nichifor Department of Economics, University of Melbourne Michael Ostrovsky Graduate School of Business, Stanford University and National Bureau of Economic Research Alexander Westkamp Department of Management, Economics, and Social Sciences, University of Cologne In a general model of trading networks with bilateral contracts, we propose a suitably adapted chain stability concept that plays the same role as pairwise stability in two-sided settings. We show that chain stability is equivalent to stability if all agents’ preferences are jointly fully substitutable and satisfy the Laws of Aggregate Supply and Demand. Inthe special case of trading networks with transferable utility, an outcome is consistent with competitive equilibrium if and only if it is chain stable. John William Hatfield: [email protected] Scott Duke Kominers: [email protected] Alexandru Nichifor: [email protected] Michael Ostrovsky: [email protected] Alexander Westkamp: [email protected] An extended abstract of this work appeared in the Proceedings of the 2018 ACM Conference on Economics and Computation. We are grateful to Dirk Bergemann, Ozan Candogan, Vincent Crawford, Dave Donaldson, Tamás Fleiner, Ravi Jagadeesan, Alessandro Pavan, Alvin Roth, Alex Teytelboym, Rakesh Vohra, several referees, and the editor, Federico Echenique, for helpful comments and suggestions. We thank Joseph Shayani for excellent research assistance. Kominers thanks the National Science Foundation (Grants CCF1216095 and SES-1459912, as well as a graduate research fellowship), the Harvard Milton Fund, the Yahoo! Key Scientific Challenges Program, the John M. Olin Center (a Terence M. Considine Fellowship), the Ng Fund and the Mathematics in Economics Research Fund of the Harvard Center of Mathematical Sciences and Applications, the American Mathematical Society, the Simons Foundation, and the University of Melbourne (the Centre for Market Design and an Eminent Research Scholar Award) for support. Nichifor received funding from the Australian Research Council under the Discovery Early Career Research Award DE170101183. Ostrovsky thanks the Alfred P. Sloan Foundation for financial support. Westkamp received funding from the German Science Foundation and from the People Programme (Marie Curie IntraEuropean Fellowship) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA Grant agreement 628276. ©2021 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE3839 198 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) Keywords. Matching, trading networks, chain stability, stability, competitive equilibria, full substitutability, Laws of Aggregate Supply and Demand. JEL classification. C78, D85, L14. 1. Introduction Cooperative solution concepts in game theory often rely on coordinated deviations by large groups of agents, including, in some cases, all the agents in the economy. A natural question when considering coordinated deviations is how (and whether) such coalitions can, in fact, form. Do all the agents in the economy need to consider all the possible deviations by all the possible coalitions? Alternatively, is it perhaps sufficient for agents to consider only smaller or more structured types of deviations? Do the agents need to reason about the structure of the entire economy to discover a profitable deviation, or is it sufficient for each of them to consider only his or her “local” environment? Shapley and Shubik (1971), Crawford and Knoer (1981), Kelso and Crawford (1982), and Roth (1984) have shown that in two-sided matching environments with substitutable preferences, one does not need to consider coordinated deviations by large groups of agents to determine the overall stability of a matching: In two-sided one-toone and many-to-one matching markets, overall stability, along with competitive equilibrium, are both essentially equivalent to pairwise stability. Pairwise stability does not require considering coordinated deviations by complex coalitions; neither does it require specifying prices for trades that are not carried out, in contrast to competitive equilibrium for two-sided matching markets, which formally require that all trades— even those not carried out—be priced. Given that pairwise deviations are much easier for agents to discover, the equivalence results for pairwise stability mitigate potential concerns about solution concepts that are either based on discovering large-group deviations or that require that all trades, including those that are not carried out, be priced. In this paper, we establish analogous results for a very rich setting—trading networks with bilateral contracts. We allow agents to be buyers in some contracts and sellers in others, and do not impose any restrictions on the network of possible trades. In particular, the market is neither required to have a two-sided structure nor is the network of possible trades required to have a vertical structure. The model we present here is strictly more general than any of the earlier models in the literature on matching with bilateral contracts, subsuming settings with discrete and continuous prices, with quasilinear and non-quasilinear utility functions, and with and without indifferences in agents’ preferences. We prove two equivalence results. Our main result shows that if all agents’ preferences jointly satisfy the full substitutability condition and the Laws of Aggregate Supply and Demand (which we make precise in Section 2.1 by way of a condition we call monotone–substitutability), then the concept of stability (under which all possible deviations by groups of agents need to be considered) is equivalent to chain stability, under which only deviations by chains of agents need to be considered.1We also show a corollary of the main result of the present paper and the results of Hatfield et al. (2013): 1Chain stability was originally introduced by Ostrovsky (2008) for a more restrictive, vertical environment in which all trade flows in one direction, from the suppliers of basic inputs to the consumers of final outputs. Theoretical Economics 16 (2021) Chain stability in trading networks 199 In trading networks with continuously transferable utility, if all agents’ preferences are fully substitutable, then an outcome is consistent with competitive equilibrium2if and only if it is not blocked by any chain. After presenting our equivalence results, we quantify the simplicity of chain deviations relative to more general “blocking set” deviations. Formally, we show that as the size of the economy grows, the number of chains of trades (corresponding to possible blocking chains) is a vanishingly small fraction of the number of general sets of trades (corresponding to possible blocking sets).3Intuitively, just as in two-sided settings—in which it is much easier to find a pairwise block than a general blocking set—in our setting, it is much easier to find a blocking chain than a general blocking set. If the network has additional structure, the simplicity gain can be much higher than suggested by our formal counting result. For example, in the supply chain setting of Ostrovsky (2008), the number of chains grows only polynomially as a function of the number of agents, while the number of sets of contracts grows exponentially. We also present three examples demonstrating the roles that our assumptions play in the main equivalence result. The first example shows that if the preferences of some agent do not satisfy the Laws of Aggregate Supply and Demand, then chain stable outcomes may not be stable. The second example shows that if the preferences of some agent are not fully substitutable, then chain stable outcomes may likewise not be stable. The third example illustrates that ensuring robustness to blocking chains that do not “cross” themselves (i.e., chains that involve each agent in at most two contracts) is not sufficient to ensure robustness to general blocking sets. This last example, combined with our equivalence results, illustrates that chain stability plays the same role in the trading network setting as pairwise stability does in two-sided settings: chains are the “essential” blocking sets that one needs to consider to evaluate an outcome’s stability or its consistency with competitive equilibrium. The model of trading networks that we consider is deliberately very general, encompassing many existing matching models and going beyond them. As a result, the existence of stable outcomes in our full model is not guaranteed (although it is, of course, guaranteed in many important special cases, such as the quasilinear case with transferable utility considered by Hatfield et al. 2013 and the vertical supply chain setting of Ostrovsky 2008). The motivation for considering such a general model is twofold: First, our model allows us to uncover the unifying structure underlying the equivalence between stability and chain stability. Second, and relatedly, we establish that checking whether an outcome is chain stable is sufficient to ensure that it is stable under larger and more general deviations. In the Ostrovsky (2008) setting, any chain of contracts has a beginning and an end, and passes “through” each agent at most once. In the current, richer environment, we adapt the definition of a chain to allow a chain to end at the same node at which it began (thus becoming a “loop”), and to cross itself (potentially several times). However, as before, the essential feature of a chain is that it is a “linked” sequence of trades, such that the agent who is the buyer in a particular trade is the seller in the next trade in the sequence. We discuss our concept of chain stability in more detail in Section 2.2 after introducing it formally. 2That is, one can generate prices for trades that are not carried out to obtain a competitive equilibrium. 3That said, Fleiner et al. (2020) showed that testing stability is NP-hard in a fully general setting; combining this with our results yields that testing chain stability is NP-hard as well. 200 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) The generality of our model allows for a wide variety of special cases. For example, following the circulation of our original draft, Fleiner et al. (2019) showed that stable outcomes are guaranteed to exist in trading network settings with income effects under full substitutability, so long as there are no frictions.4More recently, Andersson et al. (forthcoming) developed a model of time banks in which agents exchange discrete units of time performing a particular task, and Manjunath and Westkamp (2019)considered the exchange of indivisible shifts among a group of workers. All of these applications can be embedded into our model, and our results transfer over.5 The remainder of the paper is organized as follows. Section 1.1 provides an overview of the related literature. Section 2 introduces our general model. Section 3 states and proves the main result on the equivalence of stability and chain stability. Section 4 discusses the correspondence between chain stable outcomes and competitive equilibria for the special case of quasilinear preferences and fully transferable utility. Section 5 assesses the simplicity of checking chain stability relative to checking stability directly. Section 6 presents the examples that show the roles of our assumptions. Section 7 concludes. 1.1 Related literature The concept of blocking is fundamental in the analysis of matching markets. In the original papers of Gale and Shapley (1962)andShapley and Shubik (1971) on stability in two-sided markets, attention is restricted to pairwise blocks, i.e., pairs of agents who mutually prefer each other to their assigned partners. The requirement that a two-sided matching be pairwise stable—i.e., be robust to pairwise blocks—seems much weaker than the requirement that a matching be robust to deviations by arbitrary sets of agents. Indeed, in general, in markets in which some agents are allowed to match with multiple partners, a matching that is robust to deviations by pairs may not be robust to richer deviations.6However, as we discussed in the Introduction, key results in the theory of two-sided, many-to-one matching show that when agents’ preferences are substitutable (Kelso and Crawford 1982,Roth 1984), pairwise relationships are, in fact, the essential blocking sets: any pairwise stable matching is also robust to larger deviations.7 Ostrovsky (2008) introduced a generalization of two-sided matching to “supply chain” environments. In supply chain matching, goods flow downstream from initial producers to end consumers, potentially with numerous intermediaries in between. In the Ostrovsky (2008) framework, attention is restricted to blocking chains—sequences 4Their work is a strict generalization of the model of Hatfield et al. (2013) in that it goes beyond quasilinearity and allows for certain income effects in agents’ utility functions. 5Our work immediately implies that chain stability is equivalent to stability in the settings of Andersson et al. (forthcoming) and Manjunath and Westkamp (2019); meanwhile, the equivalence applies in the setting of Fleiner et al. (2019) whenever agents’ preferences are monotone–substitutable. 6For example, if every firm in an economy is only interested in hiring an even number of workers, then an empty matching will always be pairwise stable, even in the cases in which another, nonempty matching makes all agents in the economy strictly better off. 7Hatfield and Kominers (2017) prove this result in a general two-sided matching setting with contracts, and provide an overview of earlier literature on related results in other two-sided settings. Theoretical Economics 16 (2021) Chain stability in trading networks 201 of agents who could benefit from recontracting with each other along a vertical chain. Outcomes robust to chain deviations are said to be chain stable. Chain stability is a natural extension of pairwise stability to the setting in which an agent can be both a buyer and a seller; for example, an agent may be willing to sell a unit of output only if he can buy a unit of input required to produce that output. Ostrovsky (2008) showed that when the preferences of all agents in the economy are fully substitutable (see Definition 1 in Section 2.1), chain stable outcomes are guaranteed to exist. Again, chain stability appears to be a much weaker condition than the requirement that an outcome be robust to deviations by arbitrary sets of agents. However, as in the case of pairwise stability, under the assumption that agents’ preferences are fully substitutable, chains are the essential blocking sets in the supply chain setting: Hatfield and Kominers (2012)showed that in that setting, any chain stable outcome is stable, in the sense that it is robust to blocks by arbitrary sets of agents.8 Hatfield et al. (2013) dispensed with the vertical structure of the supply chain environment and instead considered arbitrary trading networks. They also assumed that prices can vary freely (instead of being restricted to a finite discrete set) and that agents’ preferences are quasilinear.9In their analysis, Hatfield et al. (2013) considered a stability concept analogous to that of Hatfield and Kominers (2012), allowing for recontracting by arbitrary groups of agents. They showed that when agents’ preferences are fully substitutable, stable outcomes exist and are essentially equivalent to competitive equilibria with personalized prices. Our model includes the setting of Hatfield et al. (2013)asa special case—and for that special case, a corollary of our main result is that an outcome is consistent with competitive equilibrium if and only if it is not blocked by any chain of contracts. Our paper contributes to the literature on the relationships between different solution concepts in matching environments (see, e.g., Echenique and Oviedo 2006,Klaus and Walzl 2009,Westkamp 2010,andHatfield and Kominers 2017). It also has parallels in the operations research literature on flows in networks (see, e.g., a textbook treatment by Ahuja et al. 1993); the “flow decomposition lemma” in that literature states that any 8The setting of Hatfield and Kominers (2012) is a special case of our framework, and for that special case, the Hatfield and Kominers (2012) definition of stability coincides with ours (Definition 4 in our Section 2.2). Note, however, that even in the case of vertical networks, our setting is substantially more general than that of Ostrovsky (2008) and Hatfield and Kominers (2012): we allow for arbitrary sets of contracts (as opposed to just finite ones) and explicitly incorporate the case in which an agent may be indifferent between two different sets of contracts (as opposed to having strict preferences); these generalizations are necessary to define the concept of competitive equilibrium and to establish the connections between chain stable outcomes and competitive equilibria. 9If one dispenses with supply chain structure without assuming that prices can vary freely, then stable outcomes may not exist (Hatfield and Kominers 2012). Fleiner et al. (2018) introduced a weaker concept, trail stability, for settings without supply chain structure. As Fleiner et al. (2018) explained (emphasis in original): “In a trail-stable outcome, no agent wants to drop his contracts and there exists no sequence of consecutive bilateral contracts [...] such that any intermediate agent who is offered a downstream (upstream)contract[...] wantstochooseitalongsidethesubsequentupstream(downstream)contract[...]. Importantly, [trail stability] require[s] that the first (final) agent wants to unilaterally offer (accept) the first (final)contract[...].” Fleiner et al. (2018) showed that trail-stable outcomes are guaranteed to exist under full substitutability (in arbitrary trading networks). 202 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) “flow” in a network can be “decomposed” into a collection of simple “paths” and “cycles,” resembling the decomposition of any blocking set into a collection of blocking chains in our Theorem 2. Note, however, that paths and cycles in the flow decomposition lemma cannot cross themselves, while in our environment, we need to allow for the possibility of self-crossing chains (see Example 3 in Section 6). The difficulty is due to the fact that in the “network flows” environment, there is a single type of good “flowing” through the network, and the objective function is the maximization or minimization of the aggregate flow, whereas in our setting many different types of goods may be present and the preferences of agents in the market may be more complex. For the case of quasilinear environments with transferable utility, Candogan et al. (2019) provided a detailed analysis of the connections between results on stability and competitive equilibrium in trading networks and the literature on network flows.10 2. Model There is an economy with a finite set Iof agents. Pairs of agents can participate in bilateral trades.Eachtradeωis associated with a buyer b(ω) ∈Iand a seller s(ω) ∈I,with b(ω) =s(ω).Thetradeωspecifies all the nonpecuniary terms and conditions associated with a relationship between b(ω) and s(ω); for instance, ωcould specify the transfer of a single unit of an indivisible good or service from s(ω) to b(ω).11 The set of possible trades, denoted , is finite and exogenously given. Note that we require that the buyer and the seller associated with a trade be distinct agents, but we allow to contain multiple trades associated with the same agents, and allow for the possibility of trades ω∈ and ψ∈such that s(ω) =b(ψ) and s(ψ) =b(ω). To capture the purely financial aspect of a transaction associated with a trade, we augment each trade by introducing a price. Formally, a contract xis a pair (ω pω)∈ ×Rthat specifies a trade and an associated price. For a contract x=(ωpω),we denote by b(x) ≡b(ω) and s(x) ≡s(ω) the buyer and the seller associated with the trade ωof x.Ifb(x) =ifor some contract x,thenxis upstream of, or on the buy-side for, i; similarly, if s(x) =ifor some contract x,thenxis downstream of, or on the sell-side for, i. We denote by X⊆×Rthe set of all contracts available to the agents; this set is fixed and exogenously given. The set Xcan be infinite (as, e.g., in the settings of Hatfield et al. 2013 and Fleiner et al. 2019, where all prices are allowed for all trades and, thus, X=×R) or finite (as, e.g., in the settings of Ostrovsky 2008,Hatfield and Kominers 2012,andFleiner et al. 2018). For each agent i∈Iand set of contracts Y⊆X,weletY→i≡{y∈Y:i=b(y)}denote the set of contracts in Yin which iis the buyer, i.e., the set of upstream contracts for i, and we let Yi→≡{y∈Y:i=s(y)}denote the set of contracts in Yin which iis the 10Beyond their conceptual interest, our results may contribute to the emerging empirical and econometric literature on matching and trading networks (see, e.g., Fox 2017). 11For some applications, the assignment of buyer and seller roles in a trading relationship follows immediately from the context. In other applications, one needs a convention. For instance, in a two-sided matching market without transfers, we think of agents on one side as sellers (in all possible outcomes) and agents on the other side as buyers (in all possible outcomes). Theoretical Economics 16 (2021) Chain stability in trading networks 203 seller, i.e., the set of downstream contracts for i.WeletYi≡Yi→∪Y→i.Weleta(Y) ≡ y∈Y{b(y)s(y)}denote the set of agents involved in contracts in Yas either buyers or sellers. Slightly abusing notation, for a contract x∈X,wewritea(x) ≡a({x}).Weuse analogous notation for various properties of trades ω∈and sets of trades ⊆: e.g., a(ω) ≡{b(ω)s(ω)}and i≡{ω∈:i∈a(ω)}. Finally,wedenotebyτ(Y) the set of trades involved in contracts in Y:τ(Y) ≡{ω∈:(ω pω)∈Yfor some pω∈R}. A set of contracts Y⊆Xis feasible if it does not contain two or more contracts associated with the same trade: formally, Y⊆Xis feasible if (ω pω) (ω ˆ pω)∈Yimplies that pω=ˆ pω; equivalently, Y⊆Xis feasible if |Y|=|τ(Y)|.Anoutcome is a feasible set of contracts. 2.1 Preferences Each agent ihas a utility function Uiover feasible sets Y⊆Xiof contracts that involve i as the buyer or the seller. For a feasible set Y⊆Xi,wehavethatUi(Y) ∈R∪{−∞},with the value of −∞used to denote sets of contracts that are technologically impossible for theagenttoundertake(e.g.,sellingthesameobjecttotwodifferentbuyers).Weassume that Ui(∅)∈R, i.e., any agent’s utility from the “outside option” of not participating in any contracts is finite. The choice correspondence of agent ifrom a set of contracts Y⊆Xiis defined as the collection of sets of contracts maximizing the utility of agent i: Ci(Y) ≡Z⊆Y:Zis feasible; ∀feasible Z⊆Y Ui(Z) ≥UiZ12 For notational convenience, we also extend the choice correspondence to sets of contracts that do not necessarily involve agent i: for a set of contracts Y⊆X,wewrite Ci(Y) ≡Ci(Yi). We now introduce our first key condition on preferences: full substitutability.13 Definition 1. The preferences of agent iare fully substitutable if both: (i) for all sets of contracts YZ ⊆Xisuch that |Ci(Y)|=|Ci(Z)|=1,Yi→=Zi→,and Y→i⊆Z→i, for the unique Y∗∈Ci(Y ) and Z∗∈Ci(Z),wehave Y→iY∗ →i⊆Z→iZ∗ →iand Y∗ i→⊆Z∗ i→; and (ii) for all sets of contracts YZ ⊆Xisuch that |Ci(Y )|=|Ci(Z)|=1,Y→i=Z→i,and Yi→⊆Zi→, for the unique Y∗∈Ci(Y ) and Z∗∈Ci(Z),wehave Yi→Y∗ i→⊆Zi→Z∗ i→and Y∗ →i⊆Z∗ →i 12Note that Ci(Y) may be empty if Yis infinite. 13For the case of quasilinear utility functions, the full substitutability definition we use here corresponds to the CFS condition of Hatfield et al. (2019). Thus, the results of Hatfield et al. (2019) imply that (again, for the case of quasilinear utility functions) our definition is equivalent to a number of other substitutability concepts that have originated in several distinct literatures. Ostrovsky (2008) and Hatfield et al. (2013) provide detailed discussions of the implications of full substitutability in various environments. 204 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) Informally, the choice correspondence Ciis fully substitutable if, when the set of options available to ion one side expands, iboth rejects a (weakly) larger set of contracts on that side and selects a (weakly) larger set of contracts on the other side (where “larger” is understood in a set-inclusion sense). Hatfield et al. (2013,2019) have identified several economically important examples of fully substitutable preferences. The second property important for our results is that the preferences of all agents satisfy the Laws of Aggregate Supply and Demand. Definition 2. The preferences of agent isatisfy the Law of Aggregate Demand if for all sets of contracts YZ ⊆Xisuch that |Ci(Y )|=|Ci(Z)|=1,Yi→=Zi→,andY→i⊆Z→i, for the unique Y∗∈Ci(Y ) and Z∗∈Ci(Z),wehave Z∗ →i−Z∗ i→≥Y∗ →i−Y∗ i→ The preferences of agent isatisfy the Law of Aggregate Supply if for all sets of contracts YZ ⊆Xisuch that |Ci(Y)|=|Ci(Z)|=1,Yi→⊆Zi→,andY→i=Z→i,forthe unique Y∗∈Ci(Y) and Z∗∈Ci(Z),wehave Z∗ i→−Z∗ →i≥Y∗ i→−Y∗ →i Informally, the choice correspondence Cisatisfies the Law of Aggregate Demand if, when the set of options available to ias a buyer expands, the net demand of i—i.e., the difference between the number of buy-side and sell-side contracts that ichooses— (weakly) increases.14 Similarly, the choice correspondence Cisatisfies the Law of Aggregate Supply if, when the set of options available to ias a seller expands, the net supply of i—i.e., the difference between the number of sell-side and buy-side contracts that i chooses—(weakly) increases. These conditions extend the canonical Law of Aggregate Demand (Hatfield and Milgrom 2005; see also Alkan and Gale 2003) to the current setting, in which each agent can be both a buyer in some trades and a seller in others. Intuitively, if we think of each contract as specifying the transfer of an object, the Laws of Aggregate Supply and Demand require that no object can substitute for multiple other objects. Thus, when iobtains access to a new buy-side contract, the total number of buy-side contracts he chooses weakly increases (for a fixed number of sellside contracts), and, similarly, when iobtains access to a new sell-side contract, the total number of sell-side contracts he chooses weakly increases (for a fixed number of buy-side contracts).15 For instance, in the setting of the used car market discussed by Hatfield et al. (2013), a trade represents the transfer of an automobile, and so the Laws of Aggregate Supply and Demand hold naturally: purchasing an additional car enables the dealer to sell at most one more car. 14That is, when an agent gains access to more buy-side contracts while holding his set of available sellside contracts fixed, the increase in the number of buy-side contracts chosen has to be weakly larger than the increase in the number of sell-side contracts chosen. 15Of course, these monotonicity conditions only make sense if trades represent corresponding units of goods; see Hatfield and Kominers (2017) for a discussion of this and other issues related to contract design. Theoretical Economics 16 (2021) Chain stability in trading networks 211 because Zblocks A, i.e., every contract in Zis chosen from Z∪A, and so every contract in W⊆Zis chosen from ((Z ∪A) W)∪W=Z∪A. Second, by construction, every agent chooses all of their contracts in ZWfrom (Z ∪A) W;thus,ZWblocks A. The full proof of Lemma 2 follows the sketch just described, but the execution is much more challenging due to the need to account for multivalued choice correspondences.20 3.1 Proof of Lemma 2 We first define the A-endowed utility function ˆ Ui(·;A) for each i∈Ias ˆ Ui(Y;A) ≡max ¯ A⊆AUi(Y ∪¯ A); that is, ˆ Ui(Y;A) is the maximum utility that agent ican obtain by combining Ywith elements of A. This gives rise to an A-endowed choice correspondence ˆ Ci(·;A) for each i∈I,givenby ˆ Ci(Y;A) ≡argmax ¯ Y⊆Yˆ Ui(¯ Y;A)=˜ YA:˜ Y∈Ci(Y ∪A); that is, an element of ˆ Ci(Y;A) is a set of contracts that i“chooses” from Ywhen he has access to all the contracts in A. Note that since Zis a blocking set, Zi⊆Yfor all Y∈Ci(Z ∪A) for all i∈Iand, thus, ˆ Ci(Z;A) ={Zi}for all i∈I. Take any contract z0∈Z. We algorithmically “grow” a chain Wcontaining z0by proceeding upstream and downstream from z0. Specifically, in a sequence of steps from z0, we grow a quasi-removable chain, i.e., a chain W={z−mz0zn}such that ZW is a blocking set except (possibly) for the buyer of znand the seller of z−m. We first proceed downstream, showing that after each step, either ZWbehaves like a blocking set for the buyer of zn, in which case znis a terminal contract, or we can extend the quasi-removable chain Wat least one step further. We then proceed upstream analogously. Once we have found the downstream and upstream terminal contracts, our quasi-removable chain Wis in fact “removable” from the blocking set Z,inthesense that ZWblocks A, as desired. We now formally define what it means for a chain to be quasi-removable. Definition 7. A chain W−mn ={z−mzn}is quasi-removable under the following conditions: (i) For all i∈I{s(z−m)b(zn)},wehavethat{[ZW−mn]i}= ˆ Ci(Z W−mn;A). 20Our formal proof follows the sketch just presented, but allows for cases in which the choice correspondence is not single-valued. In particular, we cannot use Lemma 1, as it does not allow us to characterize Cb(z0)((Z {z0})∪A) if the choice correspondence Cb(z0)(Z ∪A) is not single-valued; rather, we need to prove an analogue to the conclusion of Lemma 1 that accounts for the fact that Cb(z0)(Z ∪A) may be multivalued. Similarly, we need to prove an analogue to the conclusion of Lemma 1 for the case in which a chain “self-crosses.” 212 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) (ii) If b(zn)=s(z−m), then, when choosing from ZW−mn, we have that both: (a) the buyer of znnever drops a contract for which he is the buyer and drops at most one contract for which he is the seller, i.e., we have for all ˆ Z∗∈ˆ Cb(zn)(Z W−mn;A) that ˆ Z∗ →b(zn)=ZW−mn→b(zn) and either ˆ Z∗ b(zn)→=ZW−mnb(zn)→ or there exists a zn+1∈Zb(zn)→such that ˆ Z∗ b(zn)→=ZW−mn ∪zn+1b(zn)→; and (b) the seller of z−mnever drops a contract for which he is the seller and drops at most one contract for which he is the buyer, i.e., we have for all ˆ Z∗∈ˆ Cs(z−m)(Z W−mn;A) that ˆ Z∗ s(z−m)→=ZW−mns(z−m)→ and either ˆ Z∗ →s(z−m)=ZW−mn→s(z−m) or there exists a z−m−1∈Z→s(z−m)such that ˆ Z∗ →s(z−m)=ZW−mn ∪z−m−1→s(z−m) (iii) If b(zn)=s(z−m)=k, then when choosing from ZW−mn,agentkdrops at most one contract for which he is the buyer and at most one contract for which he is the seller, i.e., we have for all ˆ Z∗∈ˆ Ck(Z W−mn;A) that both: (a) either ˆ Z∗ →k=ZW−mn→k or there exists a z−m−1∈Z→ksuch that ˆ Z∗ →k=ZW−mn ∪z−m−1→k; and Theoretical Economics 16 (2021) Chain stability in trading networks 213 (b) either ˆ Z∗ k→=ZW−mnk→ or there exists a zn+1∈Zk→such that ˆ Z∗ k→=ZW−mn ∪zn+1k→ The first condition of Definition 7 ensures that each agent not associated with either end of the chain chooses all of the contracts in ZW−mn that he is associated with. The second condition of Definition 7 ensures that when each end of the chain is associated with a different agent, the agent at each end chooses all but one contract in ZW−mn that he is associated with. The third condition of Definition 7 ensures that when each end of the chain is associated with the same agent, that agent chooses all of the contracts in ZW−mn that he is associated with except for possibly one contract as a buyer and possibly one contract as a seller. We say that a quasi-removable chain W−mn ={z−mzn}is (i) downstream terminal if b(zn)strictly demands all of the contracts for which he is a seller, i.e., for all ˆ Z∗∈ˆ Cb(zn)(Z W−mn;A),wehavethat ˆ Z∗ b(zn)→=ZW−mnb(zn)→ and (ii) upstream terminal if s(z−m)strictly demands all of the contracts for which he is a buyer, i.e., for all ˆ Z∗∈ˆ Cs(z−m)(Z W−mn;A),wehavethat ˆ Z∗ →s(z−m)=ZW−mn→s(z−m) We now present a series of five claims, all proven in Appendix A, that we combine to establish Lemma 2. Claim 1. Consider any z0∈Z. Then W00≡{z0}is a quasi-removable chain. Claim 1 shows that for any arbitrary element z0∈Z,thesetW00≡{z0}is a quasiremovable chain. Our next claim shows that any blocking chain that is not downstream terminal can be extended into a longer quasi-removable chain through the addition of a downstream contract. Claim 2. Suppose that W−mn ={z−mzn}is a quasi-removable chain that is not downstream terminal. Then there exists a zn+1such that s(zn+1)=b(zn)and such that W−mn+1≡W−mn ∪{zn+1}is a quasi-removable chain. Moreover, if W−mn is upstream terminal, then W−mn+1is upstream terminal. An analogous result holds upstream: any blocking chain that is not upstream terminal can be extended into a longer quasi-removable chain through the addition of an upstream contract. 214 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) Claim 3. Suppose that W−mn ={z−mzn}is a quasi-removable chain that is not upstream terminal. Then there exists a z−m−1such that b(z−m−1)=s(z−m)and such that W−m−1n ≡W−mn ∪{z−m−1}is a quasi-removable chain. Moreover, if W−mn is downstream terminal, then W−m−1n is downstream terminal. Our next claim ensures that once we have found a quasi-removable chain that is both downstream and upstream terminal, then that quasi-removable chain is, in fact, a blocking chain. Claim 4. If W−mn ={z−mzn}is a downstream and upstream terminal quasiremovable chain, then ZW−mn blocks A. Our last claim verifies that any subset Wof a blocking set Zblocks A∪(Z W). Claim 5. Any nonempty W⊆Zblocks A∪(Z W). We now complete the proof of Lemma 2 by way of our claims. Consider any z0∈Z; by Claim 1,wehavethatW00={z0}is a quasi-removable chain. If W00is not downstream terminal, then by Claim 2,thereexistsaz1such that s(z1)=b(z0)and such that W01={z0z1}is a quasi-removable chain. Proceeding inductively, any quasi-removable chain W0n ={z0zn}that is not downstream terminal can be extended to a quasiremovable chain W0n+1=W0n ∪{zn+1}by adding one sell-side contract zn+1for the buyer of zn. Since Zis finite and all the quasi-removable chains are contained in Z, this downstream extension process must eventually end at a quasi-removable chain W0N that is downstream terminal. Similarly, if W0N is a quasi-removable chain that is downstream but not upstream terminal, then by Claim 3,thereexistsaz−1such that W−1N =W0N ∪{z−1}is a downstream terminal quasi-removable chain. Again proceeding inductively, we can extend any downstream but not upstream terminal quasiremovable chain W−mN to a downstream terminal quasi-removable chain W−m−1N , until we reach a quasi-removable chain W−MN that is downstream and upstream terminal. Finally, by Claims 4and 5,ZW−MN must block Aand W−MN must block A∪(Z W−MN). 4. Chain stability and competitive equilibrium The results of Section 3 hold for general sets of contracts under monotone–substitutable preferences. For an environment in which both •prices are continuous and unrestricted, i.e., X=×R,and •agents’ preferences are quasilinear in prices, Hatfield et al. (2013) showed that when agents’ preferences are fully substitutable, an outcome is stable if and only if it is consistent with competitive equilibrium. Thus, a corollary of Theorem 1 is that in the trading network setting of Hatfield et al. (2013), an outcome is consistent with competitive equilibrium if and only if it is not blocked by a chain of contracts; for a formal statement of this result, see Appendix B. Theoretical Economics 16 (2021) Chain stability in trading networks 215 5. Quantifying the simplicity gain Theorem 1 implies that under monotone–substitutability, checking whether an outcome is stable (and in the quasilinear case, consistent with competitive equilibrium) reduces to checking whether that outcome is chain stable. In this section, we examine theextenttowhichTheorem 1 simplifies checking stability. We first consider asymptotics as the economy grows large; then we discuss computational complexity aspects. 5.1 Asymptotic simplicity gains We show that while checking directly whether a given outcome Yis stable requires checking 2|XY|possible blocking sets, the reduction to chain stability leads to a significant asymptotic simplicity gain, in the sense that the proportion of possible blocking sets that are chains goes to 0as the economy grows large.21 Formally, we define a sequence of economies (I m)∞ m=1as having a fixed set of agents Iand a sequence of finite sets of trades 12 such that |m|=m.Fora given ω∈∞ m=1m,letP(ω) ⊆Rbe the set of possible prices for ω; that is, we assume that the set of possible prices associated with a given trade ωdoes not vary with m.For the economy (I m), the set of contracts is given by Xm≡ω∈mp∈P(ω){(ω p)}.22 Note that checking the stability of an outcome Yfor the economy (I m)may require checking blocking sets corresponding to any set of trades in Bm(Y) ≡⊆mτ(Y) By contrast, checking the chain stability of an outcome Yfor the economy (I m)requires checking blocking chains corresponding to any chain of trades in Cm(Y) ≡⊆mτ(Y) :is a chain We show that, for any fixed set of contracts Y, the ratio of [the number of distinct sets of chains of trades corresponding to possible blocking chains] to [the number of distinct sets of trades corresponding to possible blocking sets], i.e., |Cm(Y )| |Bm(Y)|,goesto0as mgrows large. Theorem 3. For any sequence of economies (I m)∞ m=1such that |m|=mfor all m,for any Y, we have that Cm(Y ) Bm(Y)=Olog2m √m In particular, |Cm(Y )| |Bm(Y)|→0as m→∞. 21Intuitively, we show that as we randomly add trades and the economy grows large, the probability that an arbitrary blocking set is a chain goes to 0. 22Our modeling in this section is deliberately parsimonious. Since the results in this section rely exclusively on combinatorial arguments regarding the number of chains and sets of trades that need to be considered, our requirements that the set of agents Iis fixed and that the set of possible prices associated with a trade is invariant across economies could both be relaxed, e.g., allowing the sets of agents and prices to vary with mwould not affect our results. 216 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) Theorem 3 follows from a general graph-theoretic result proven by Shayani (2018). In Appendix C, we present a formal proof of Theorem 3, adapting the argument of Shayani (2018) to our setting. To understand the intuition behind Theorem 3, consider a directed multi-graph with the set of vertices Iand the set of edges having one edge for each trade in m, directed from the seller to the buyer of that trade. To determine what proportion of the subsets of mconsists of chains, we proceed via a probabilistic argument: We consider a random set of trades chosen from mby including each trade ω∈min independently with probability 1 2. For a random set of trades to be a chain, the following two “balancedness” requirements have to be satisfied: (i) For each agent i∈a(), the number of contracts in which that agent is the buyer differs by at most 1from the number of contracts in which he is the seller, i.e., ||→i|−|i→||≤1. (ii) There are at most two distinct agents j∈a() who sign different numbers of contracts as a buyer and as a seller, i.e., there are at most two distinct agents j∈a() for whom |→j|−|j→|=0. These balancedness requirements follow directly from the definition of a chain (Definition 5), as the buyer of the first trade is the seller of the second trade, the buyer of the secondtradeisthesellerofthethirdtrade,...,andthebuyerofthe(||−1)-st trade is the seller of the ||-th trade; thus, only the seller of the first trade and the buyer of the ||-th trade can sign different numbers of contracts as a buyer and a seller. For the random set of trades , there are two cases to consider. Large agent case: In this case, there is one “large” agent i, who is involved in many of the mtrades in . Many small agents case: In this case, there are many “small” distinct agents, each of whom is involved in a few trades in . In the large agent case, we show that the probability that the first balancedness condition is satisfied for a “big” agent iis small because it is unlikely that iwill have roughly equal numbers of contracts in which he is a buyer and in which he is a seller, as he is involved in many trades in the random set . In the many small agents case, we show that the probability that is such that |→j|−|j→|=0for all but two agents jis small, so it is unlikely that the second balancedness condition is satisfied. Combining thepreceding two results shows that, in the limit, very few random sets of trades will be chains. Theorem 3 implies that for general trading networks, the ratio of chains to the total number of subsets converges to 0as the number of trades grows large. Thus, the set of chains is asymptotically a vanishingly small fraction of the set of potential blocking sets; consequently, checking stability by considering each possible blocking chain is asymptotically much simpler than checking stability by considering each possible blocking Theoretical Economics 16 (2021) Chain stability in trading networks 217 set.23 In fact, even for settings for which the existence of stable outcomes is not guaranteed,24 Theorem 1 implies that checking for the existence of chain stable outcomes is sufficient when agents’ preferences are monotone–substitutable, and Theorem 3 implies that checking chain stability is substantially easier than checking stability. If the trading network has additional structure, then the simplicity gain can be much higher than that implied by the bound in Theorem 3. For instance, consider the case of multilayered supply chains,álaOstrovsky (2008). In a multilayered supply chain, there are L+1layers (I)L+1 =1, which partition the set of agents; each trade “flows” one layer down the supply chain, i.e., for any trade ω∈,ifs(ω) ∈I,thenb(ω) ∈I+1. Thus, there are Lbands of trades, 1L, in between the layers of agents, such that s()⊆Iand b()⊆I+1. In this case, the total number of chains of trades is bounded by L =1(||+1), while the total number of sets of trades is given by 2|1|+···+|L|. Our results also imply (by combining Corollary 1 and Theorem 3) that checking whether an outcome is consistent with competitive equilibrium becomes straightforward in the Sun and Yang (2006,2009) environment with gross substitutes and complements. In such an environment, one side of the market is a set of buyers while the other side of the market consists of two distinct groups of objects. Buyers view objects in the same group as substitutes for each other, but view objects in different groups as complements; such preferences arise naturally when a firm has two types of complementary inputs. As Hatfield et al. (2013)showed,theSun and Yang (2006,2009) environment is a special case of the Hatfield et al. (2013) trading network framework.25 Moreover, chains in the Sun and Yang (2006,2009) environment are particularly simple: they consist either of one buyer and one object (or, more formally, one contract between a buyer and an object) or of one buyer and one object from each of the two groups (again, more formally, two contracts, involving the same buyer and two objects from different groups). Thus, checking for consistency with competitive equilibrium reduces to checking oneand two-contract blocking chains. Inthe two-sided setting of Kelso and Crawford (1982), which is itself a special case of the Sun and Yang (2006,2009) framework, our results imply that checking for consistency with competitive equilibrium reduces to checking for single-contract blocks. 5.2 Computational complexity Subsequent to the first version of this paper, a number of settings that are special cases of our model have been studied. For the special case of trading networks called flow networks, in which agents’ preferences are strict (and, thus, continuous transfers are not allowed) and there are exactly two so-called terminal agents who always choose all of the contracts that they 23However, for arbitrarily complex trading networks, Shayani(2018) showed that the bound in Theorem 3 is almost tight. 24For example, if prices are not allowed to vary freely and preferences are not quasilinear, monotone– substitutability is not, in general, sufficient to guarantee the existence of stable outcomes; see, e.g., Hatfield and Kominers (2012). 25The embedding of Hatfield et al. (2013) allows for much more general environments than those considered by Sun and Yang (2006,2009): e.g., “objects” may have preferences over whom they match with and may be involved in multiple contracts. 218 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) are involved in, Fleiner et al. (2020) showed that establishing whether a stable outcome exists is an NP-complete problem.26 Note that since the result established by Fleiner et al. (2020) is for a setting that is a special case of ours, it directly implies that checking whether a stable outcome exists remains an NP-complete problem in our setting too. For the special case of arbitrarily complex trading networks in which agents’ preferences are quasilinear in the numeraire, Candogan et al. (2019) developed a polynomial-time algorithm that, for a given outcome, either constructs a blocking chain or verifies that no such chain exists; for this case, combining the result of Candogan et al. (2019)withourTheorem 1 yields a polynomial-time algorithm for checking stability. Finally, a number of new applications can be embedded into our model for which stable outcomes can be computed efficiently. For example, Andersson et al. (forthcoming) studied the organization of time banks and Manjunath and Westkamp (2019)studied shift exchanges between workers. Both Andersson et al. (forthcoming)andManjunath and Westkamp (2019) developed algorithms that find individually rational and Pareto-efficient outcomes in polynomial time; furthermore, these outcomes turn out to be stable as well. 6. Examples The proof of our main equivalence result (Theorem 1) requires monotone– substitutability—the conjunction of full substitutability and the Laws of Aggregate Supply and Demand. In this section, we show that whenever some agent’s preferences fail to be fully substitutable or fail to satisfy the Laws of Aggregate Supply and Demand, our equivalence result may not hold. We also show that it is essential that the definition of chain stability allow chains to cross themselves, i.e., that we allow an agent to be involved in more than two contracts in a chain.27 We start with an example of preferences that are fully substitutable, but for which the Laws of Aggregate Supply and Demand do not hold—and the equivalence result does not hold either.28 Example 1. There are two agents, iand j. There are four contracts between the two agents: x,y,z,andw.Agentiis the seller of x,y,andz, and is the buyer of w, while agent jis the buyer of x,y,andz, and the seller of w. The economy is depicted in Figure 1. 26Even though Fleiner et al. (2020) did not explicitly assume that agents’ choice functions satisfy the Laws of Aggregate Supply and Demand, their results still apply in our setting, as the choice functions they used in their construction satisfy the Laws of Aggregate Supply and Demand. 27For convenience, we give our examples in terms of ordinal preference relations over sets of contracts; it is straightforward to construct corresponding cardinal utility functions over sets of contracts that give rise to these ordinal preference relations, and we omit those constructions. 28As shown by Hatfield and Kominers (2012), the Laws of Aggregate Supply and Demand are not necessary for the equivalence of stability and chain stability in the supply chain setting. The need for monoton– substitutability in our setting is because we need to allow for chains to be self-crossing—which cannot happen in supply chain networks. Theoretical Economics 16 (2021) Chain stability in trading networks 219 i xyz j w Figure 1. The economy of Example 1. Each arrow denotes a contract from its seller to its buyer. The preferences of the agents are as follows. Informally, agent iis happy to sign contract win which he is the buyer, regardless of what his options are on the other side of the market, and if (and only if) he is able to sign contract w, then he is also happy to sign any subset of the other three contracts (in which he is the seller)—the more, the better. Formally, the preferences of iover acceptable bundles of contracts are {wxyz}i{wxy}i{wxz}i{wyz}i{wx}i{wy}i{wz}i{w}i∅ Agent jis happy to sign any subset of {x y z}(in which he is the buyer)—the more, the better—no matter what his options are on the other side of the market. If (and only if) he has access to all three of x,y,andz, then he is also happy to sign contract w(in which he is the seller). Formally, the preferences of jover acceptable bundles of contracts are {wxyz}j{xy z}j{x y}j{x z}j{yz}j{x}j{y}j{z}j∅ Note first that the preferences of agents iand jare fully substitutable but also note that the preferences of agent ido not satisfy the Law of Aggregate Demand.29 The empty set of contracts, ∅, is not stable: it is blocked by the full set of contracts in the economy, {wxyz}, which is the most preferred set of contracts for both agents. At the same time, the empty set of contracts is not blocked by any chain; hence, the empty set is chain stable. To see this, note first that any blocking set would, of course, have to involve both agents. Second, every nonempty set acceptable to agent imust include contract w,sowwould have to be a part of the blocking chain. Third, the only set of contracts involving contract wthat is acceptable to agent jis the full set of contracts {wxyz}. Thus, {wxyz}is the only blocking set in this example—and it cannot be represented as a chain. ♦ Our second example shows that full substitutability likewise plays a critical role for the equivalence result: without it, chain stability is strictly weaker than stability, even when all agents’ preferences satisfy the Laws of Aggregate Supply and Demand. Example 2. There are three agents: i,j,andk. There are two contracts: xand y.Agent iis the buyer of both xand y,agentjis the seller of x, and agent kis the seller of y.The economy is depicted in Figure 2. 29Indeed, Ci({xyz})=∅while Ci({wxyz})={wxyz}, that is, the net demand of ifalls (from 0to −2)afterireceives the new buy-side offer w. 220 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) j x k y i Figure 2. The economy of Example 2. Each arrow denotes a contract from its seller to its buyer. The preferences of agents jand kare straightforward and are fully substitutable. Indeed, each agent desires to sign the contract in which he is the seller: {x} j∅and {y} k∅. The preferences of agent iare not fully substitutable: iprefers signing both contracts to signing none, but prefers not signing any contracts to signing only one contract; that is, the preferences of agent iover acceptable bundles of contracts are given by {xy}i∅. The empty set of contracts, ∅, is not stable: it is blocked by the full set of contracts in the economy, {x y}. At the same time, the empty set is chain stable: Any chain involves agent iand contains exactly one contract—and agent ifinds any such set of contracts unacceptable. ♦ Our third and final example shows that even when preferences are monotone– substitutable, it may not be sufficient to restrict attention to blocking chains that do not cross themselves. Specifically, if attention is restricted to chains in which each agent appears in at most two consecutive contracts, then an outcome that is robust to deviations by such chains may be blocked by richer sets of contracts.30 Example 3. There are three agents: i,j,andk. There are four contracts: x1,x2,y1,and y2.Agentiis the buyer of contract x1and the seller of contract y1.Agentjis the buyer of contract x2and the seller of contract y2.Agentkis the seller of contracts x1and x2and the buyer of contracts y1and y2. The economy is depicted in Figure 3. The preferences of agents iand jare straightforward: Each one prefers to sign both contracts that he is associated with and is not interested in any other nonempty set of contracts; that is, {x1y1}i∅and {x2y2}j∅. The preferences of agent kare x1x2y1y2kx1y2kx2y1k∅; agent kfinds other nonempty sets of contracts unacceptable. In this example, all agents’ preferences are monotone–substitutable. Also, the empty set of contracts is not stable, as it is blocked by the chain {x1y1x2y2}; that chain is selfcrossing—it involves agent kin all four contracts. However, no chain that does not cross 30However, the necessity of considering self-crossing chains is only present in fully general trading networks. In particular, in the supply chain setting of Ostrovsky (2008), self-crossing chains are not even possible because each agent buys only from agents upstream and sells only to agents downstream. In the supply chain setting, stability and chain stability are also equivalent to the tree stability concept of Ostrovsky (2008). Theoretical Economics 16 (2021) Chain stability in trading networks 227 Case 2: b(zn+1)=s(z−m).Ifb(zn+1)=s(z−m)≡k, then we need to check the condition (iii) of Definition 7. Analogously to Case 1, we choose an arbitrary set Y∗∈ Ck((Z W−mn+1)∪A). Note first that since Cb(zn+1)is monotone–substitutable, there exists a Z∗∈Cb(zn+1)((Z W−mn)∪A) such that ZW−mn+1∪AY∗→k⊆ZW−mn∪AZ∗→k(16) Y∗ k→⊆Z∗ k→(17) Z∗ →k−Y∗ →k≥Z∗ k→−Y∗ k→(18) Partition Y∗into ˆ Y∗≡Y∗∩(Z W−mn+1)and ˇ Y∗≡Y∗∩A, and partition Z∗into ˆ Z∗≡Z∗∩(Z W−mn)and ˇ Z∗≡Z∗∩A.35 Note that either ˆ Z∗ →k=[ZW−mn]→k or ˆ Z∗ →k=[(Z W−mn){z−m−1}]→kfor some z−m−1∈[ZW−mn]→k,asW−mn is a quasi-removable chain and b(zn)=s(z−m)inthecaseweconsiderhere. 36 We argue first that condition (iii)(a) of Definition 7 is satisfied: When zn+1is no longer available, every optimal choice by kexcludes at most one of his remaining contracts as a buyer, i.e., either ˆ Y∗ →k=[ZW−mn+1]→kor there exists a z−m−1∈Z such that ˆ Y∗ →k=[(Z W−mn+1){z−m−1}]→k.Wecanrewrite(16)as ZW−mn+1∪A→kˆ Y∗∪ˇ Y∗→k⊆ZW−mn∪A→kˆ Z∗∪ˇ Z∗→k or, equivalently, ZW−mn+1ˆ Y∗→k∪Aˇ Y∗→k⊆ZW−mnˆ Z∗→k∪Aˇ Z∗→k; given that Z∩A=∅, this subset relation implies that ZW−mn+1ˆ Y∗→k⊆ZW−mnˆ Z∗→k(19) If ˆ Z∗ →k=[ZW−mn]→k,then(19) implies that ˆ Y∗ →k⊇[ZW−mn+1]→k;but ˆ Y∗≡Y∗∩(Z W−mn+1)and so ˆ Y∗ →k=[ZW−mn+1]→k.Consequently,ifW−mn is upstream terminal (i.e., ˆ Z∗ →k=[ZW−mn]→k), then W−mn+1is upstream terminal (i.e., ˆ Z∗ →k=[ZW−mn+1]→k). If ˆ Z∗ →k=[(Z W−mn){z−m−1}]→kfor some z−m−1∈[ZW−mn]→k,then(19) implies that ˆ Y∗ →k⊇[(ZW−mn+1){z−m−1}]→k; but ˆ Y∗≡Y∗∩(Z W−mn+1)and so either ˆ Y∗ →k=[ZW−mn+1]→kor ˆ Y∗ →k= [(Z W−mn+1){z−m−1}]→k.Hence,whenzn+1is no longer available, every optimal choice by kas a buyer includes all but at most one of the contracts in [ZW−mn+1]→k. We argue second that condition (iii)(b) of Definition 7 is satisfied: When zn+1is no longer available, every optimal choice by kexcludesat most one of his remaining contracts as a seller, i.e., either ˆ Y∗ k→=[ZW−mn+1]k→or there exists a zn+2∈Zk→ such that ˆ Y∗ k→=[(Z W−mn+1){zn+2}]k→.Notefirstthat(16) implies that k 35Recall that A∩(Z W−mn+1)=∅. 36In this case, we have assumed that b(zn+1)=s(z−m)and so, since b(zn)=s(zn+1)and s(zn+1)= b(zn+1),wehavethatb(zn)=s(z−m). 228 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) chooses at most one fewer contract as a buyer when zn+1is no longer available, i.e., |Z∗ →k|−|Y∗ →k|≤1.Hence,(18) implies that |Z∗ k→|−|Y∗ k→|≤1.Wecanrewritethis last inequality as ˆ Z∗ k→−ˆ Y∗ k→+ˇ Z∗ k→−ˇ Y∗ k→≤1(20) Now by (17), we have that Y∗ k→⊆Z∗ k→and, thus, ˇ Y∗ k→⊆ˇ Z∗ k→; combining this with (20) implies that |ˆ Z∗ k→|−|ˆ Y∗ k→|≤1.Moreover,by(17), we have that Y∗ k→⊆Z∗ k→ and, thus, ˆ Y∗ k→⊆ˆ Z∗ k→; hence, either ˆ Y∗ k→=ˆ Z∗ k→or there exists a zn+2such that ˆ Y∗ k→=[ˆ Z∗{zn+2}]k→. This completes the proof of Claim 2. A.4 Proof of Claim 3 The proof follows the proof of Claim 2 mutatis mutandis. A.5 Proof of Claim 4 As W−mn is quasi-removable, we know that for all i∈I{s(z−m)b(zn)},wehavethat {[ZW−mn]i}= ˆ Ci(Z W−mn)(from condition (i) of Definition 7). There are two cases to consider: Case 1: b(zn)=s(z−m). Since W−mn is downstream terminal, we have that Zb(zn)z−mzn=ˆ Cb(zn)Zz−mzn;A Furthermore, since W−mn is upstream terminal, we have that Zs(z−m)z−mzn=ˆ Cs(z−m)Zz−mzn;A Thus, ZW−mn blocks A. Case 2: b(zn)=s(z−m). In this case, since W−mn is downstream and upstream terminal, we have that Zb(zn)z−mzn=ˆ Cb(zn)Zz−mzn;A Thus, ZW−mn blocks A. This completes the proof of Claim 4. A.6 Proof of Claim 5 As Zblocks A, for all i∈a(Z), for each Y∈Ci(A ∪Z),wehavethatZi⊆Y. Since W⊆Z, for all i∈a(Z), for each Y∈Ci(A ∪Z),wehavethatWi⊆Y. Thus, for all i∈ a(W ) ⊆a(Z), for each Y∈Ci(A ∪Z) =Ci((A ∪(Z W))∪W),wehavethatWi⊆Y. Thus, by definition, Wblocks A∪(Z W). Theoretical Economics 16 (2021) Chain stability in trading networks 229 Appendix B: Chain stability and competitive equilibrium In this appendix, we show that in the trading network setting of Hatfield et al. (2013), an outcome is consistent with competitive equilibrium if and only if it is not blocked by a chain of contracts. The Hatfield et al. (2013) setting is a special case of ours that requires that •prices are continuous and unrestricted, i.e., X=×R,and •agents’ preferences are quasilinear in prices. Formally, a utility function Uiis quasilinear in prices if there exists a valuation function uifrom the sets of trades involving agent ito R∪{−∞}such that for any feasible set Y⊆Xi, Ui(Y) =uiτ(Y)+ (ωpω)∈Yi→ pω− (ωpω)∈Y→i pω Definition 8. An outcome Yis consistent with competitive equilibrium if there exists a vector of prices for all trades in the economy, p∈R,suchthat •for every ω∈τ(Y),wehave(ω pω)∈Y,and •for every agent i, for every set of trades ⊆i,wehave Ui(Yi)≥ui() + ω∈i→ pω− ω∈→i pω An outcome Yonly specifies prices for the trades that are, in fact, executed under the outcome, while a competitive equilibrium specifies prices for all the trades in the economy. For an outcome to be consistent with competitive equilibrium, it must be that one can specify prices for the trades that are not executed so that, for each agent i, selecting the trades associated with the outcome Yis, in fact, consistent with utility maximization; Definition 8 formalizes this requirement. We are now ready to state our competitive equilibrium equivalence result. Corollary 1. Suppose that the set of contracts is X=×R, and that all agents’ preferences are fully substitutable and quasilinear in prices. Then an outcome is consistent with competitive equilibrium if and only if it is chain stable. Proof. Under the assumed conditions on Xand agents’ preferences, Theorem 10 of Hatfield et al. (2019) implies that all agents’ utility functions are monotone–substitutable. Thus, by our Theorem 1, an outcome is chain stable if and only if it is stable. Moreover, byTheorems5and6ofHatfield et al. (2013), an outcome is stable if and only if it is consistent with competitive equilibrium under fully substitutable preferences. Thus, under the assumptions of the corollary, an outcome is chain stable if and only if it is consistent with competitive equilibrium. 230 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) Appendix C: Proof of Theorem 3 Here, we implicitly use Ias the set of agents who have trades in m. For a set of agents J⊆Iand for any set of trades ⊆m,let J≡ j∈J j=ϕ∈:b(ϕ) ∈Jor s(ϕ) ∈J For a set of agents J⊆I,anagenti∈IJexpands m Jif m {i}∪Jm J=∅.Anexpanding sequence of agents is a sequence of agents (i1iR)such that irexpands m {i1ir−1} for all r=1R.Acomplete expanding sequence of agents is a sequence of agents (i1iR)such that m {i1iR}=m. Note that every set of trades can be constructed by sequentially choosing sets of trades in i1iri1ir−1for r=1R. We complete the proof by considering two mutually exclusive cases: In the first case, we assume that there exists an agent associated with at least m log2(m) trades; in the second case, since no agent is associated with m log2(m) or more trades, any complete expanding sequence must contain at least log2(m) agents. In each case, we construct a bound on the ratio of the number of chains to the number of potential blocking sets. Case 1: A large agent. Here, we suppose that there exists an agent isuch that |m i|≥ m log2(m) . For a set of trades ⊆mto be a chain, it must be the case that either |→i|= |i→|,|→i|=|i→|+1(when iis at the downstream end of the chain) or |→i|+ 1=|i→|(when iis at the upstream end of the chain). We compute that: – the number of the sets of trades satisfying the first of these three criteria is |m →i|  n=0m →i nm i→ n=m i m →i≤⎛ ⎝m i m i 2 ⎞ ⎠; – the number of the sets of trades satisfying the second of these three criteria is |m →i|  n=0m →i n+1m i→ n=m i m →i−1≤⎛ ⎝m i m i 2 ⎞ ⎠; – the number of the sets of trades satisfying the third of these three criteria is |m →i|  n=0m →i nm i→ n+1=m i m →i+1≤⎛ ⎝m i m i 2 ⎞ ⎠ Summing the three previous expressions, we find that the number of sets of trades satisfying one of our three conditions is no greater than 3⎛ ⎝m i m i 2 ⎞ ⎠ Theoretical Economics 16 (2021) Chain stability in trading networks 231 Thus, using Stirling’s bounds, we find that the number of chains of trades is no greater than 32 π⎛ ⎝ 2|m i| m i⎞ ⎠ Thus,asthenumberofsubsetsoftradesissimply2|m i|,wehavethat |Cm(Y)| |Bm(Y)|= O(√log2m √m)as |m i|≥ m log2(m) . Case 2: Small agents. Here we suppose that |m i|<m log2(m) for all i∈I.Thus, there must exist a complete expanding sequence of agents (i1iR)such that R≥log2(m). It is easy to compute that, as m i1is nonempty, the following inequality holds:37 W1⊆m i1:W1 →i1=W1 i1→ W1⊆m i1≤1 2 That is, the number of subsets of m i1that are “balanced for i1”(i.e.,suchthati1 is associated with the same number of buy and sell contracts) is at most half of the number of subsets of m i1. We can also compute, taking any sequence W1Wr−1, where Wris chosen from m {i1ir}, that (recalling that (i1iR)is an expanding sequence) Wr⊆m {i1ir}m {i1ir−1}:r  s=1 Ws→ir=r  s=1 Wsir→ Wr⊆m {i1ir}m {i1ir−1}≤1 2 That is, taking any sequence W1Wr−1,whereWris chosen from m {i1ir},the number of subsets of m {i1ir}m {i1ir−1}such that r s=1Wsis “balanced for ir”is at most half of the number of subsets of m {i1ir}m {i1ir−1}. Using the preceding two observations, if we construct a set by choosing trades in this way along the complete expanding sequence, the overall probability that each agent iris balanced is bounded by 1 2R  37This follows as we can compute {W1⊆m i1:|W1 →i1|=|W1 i1→|}as the sum over |m →i1|  n=0m →i1 nm i1→ n=m i1 m →i1≤⎛ ⎜ ⎝m i1 m i1 2⎞ ⎟ ⎠≤2|m i1|−1 232 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) Similarly, the overall probability that each agent irexcept one is balanced is bounded by R 11 2R−1  Finally, the overall probability that each agent irexcept for two is balanced is bounded by R 21 2R−2  Summing the three preceding expressions, we compute that the probability that a set of trades constructed by choosing each trade in mwith probability 1 2is a chain is no more than 1 2R +R 11 2R−1 +R 21 2R−2 ≤4R21 2R  Recalling that R≥log2(m),wehavethat |Cm(Y)| |Bm(Y)|=O(log2(m))2 mOlog2m √m References Ahuja, Ravindra K., Thomas L. Magnanti, and James B. Orlin (1993), Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, N.J. [201] Alkan, Ahmet and David Gale (2003), “Stable schedule matching under revealed preference.” Journal of Economic Theory, 112, 289–306. [204] Andersson, Tommy, Ágnes Cseh, Lars Ehlers, and Albin Erlanson (forthcoming), “Organizing time exchanges: Lessons from matching markets.” American Economic Journal: Microeconomics.[200,218] Candogan, Ozan, Markos Epitropou, and Rakesh V. Vohra (2019), “Competitive equilibrium and trading networks: A network flow approach.” Working paper, SSRN 2738610. [202,218] Crawford, Vincent P. and Elsie Marie Knoer (1981), “Job matching with heterogeneous firms and workers.” Econometrica, 49, 437–450. [198] Echenique, Federico and Jorge Oviedo (2006), “A theory of stability in many-to-many matching markets.” Theoretical Economics, 1, 233–273. [201] Fleiner, Tamás, Ravi Jagadeesan, Zsuzsanna Jankó, and Alexander Teytelboym (2019), “Trading networks with frictions.” Econometrica, 87, 1633–1661. [200,202] Fleiner, Tamás, Zsuzsanna Jankó, Ildikó Schlotter, and Alexander Teytelboym (2020), “Complexity of stability in trading networks.” Working paper, arXiv:1805.08758.[199, 218] Theoretical Economics 16 (2021) Chain stability in trading networks 233 Fleiner, Tamás, Zsuzsanna Jankó, Akihisa Tamura, and Alexander Teytelboym (2018), “Trading networks with bilateral contracts.” Working paper, SSRN 2457092. [201,202] Fox, Jeremy T. (2017), “Specifying a structural matching game of trading networks with transferable utility.” American Economic Review, 107, 256–260. [202] Gale, David and Lloyd S. Shapley (1962), “College admissions and the stability of marriage.” American Mathematical Monthly, 69, 9–15. [200] Hatfield, John William and Scott Duke Kominers (2012), “Matching in networks with bilateral contracts.” American Economic Journal: Microeconomics, 4, 176–208. [201,202, 207,217,218] Hatfield, John William and Scott Duke Kominers (2017), “Contract design and stability in many-to-many matching.” Games and Economic Behavior, 101, 78–97. [200,201,204] Hatfield, John William, Scott Duke Kominers, Alexandru Nichifor, Michael Ostrovsky, and Alexander Westkamp (2013), “Stability and competitive equilibrium in trading networks.” Journal of Political Economy, 121, 966–1005. [198,199,200,201,202,203,204, 207,214,217,229] Hatfield, John William, Scott Duke Kominers, Alexandru Nichifor, Michael Ostrovsky, and Alexander Westkamp (2019), “Full substitutability.” Theoretical Economics, 14, 1535– 1590. [203,204,205,207,229] Hatfield, John William and Paul R. Milgrom (2005), “Matching with contracts.” American Economic Review, 95, 913–935. [204,207] Kelso, Alexander S. and Vincent P. Crawford (1982), “Job matching, coalition formation, and Gross substitutes.” Econometrica,50, 1483–1504. [198,200,217] Klaus, Bettina and Markus Walzl (2009), “Stable many-to-many matchings with contracts.” Journal of Mathematical Economics, 45, 422–434. [201] Manjunath, Vikram and Alexander Westkamp (2019), “Strategy-proof exchange under trichotomous preferences.” Working paper, Department of Management, Economics and Social Sciences, University of Cologne. [200,218] Ostrovsky, Michael (2008), “Stability in supply chain networks.” American Economic Review, 98, 897–923. [198,199,200,201,202,203,207,208,217,220] Roth, Alvin E. (1984), “Stability and polarization of interests in job matching.” Econometrica, 52, 47–58. [198,200] Shapley, Lloyd S. and Martin Shubik (1971), “The assignment game I: The core.” International Journal of Game Theory, 1, 111–130. [198,200] Shayani, Joseph (2018), “How many subsets of edges of a directed multigraph can be represented as trails?” Working paper, arXiv:1606.09107.[216,217] Sun, Ning and Zaifu Yang (2006), “Equilibria and indivisibilities: Gross substitutes and complements.” Econometrica, 74, 1385–1402. [217] 234 Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp Theoretical Economics 16 (2021) Sun, Ning and Zaifu Yang (2009), “A double-track adjustment process for discrete markets with substitutes and complements.” Econometrica, 77, 933–952. [217] Westkamp, Alexander (2010), “Market structure and matching with contracts.” Journal of Economic Theory, 145, 1724–1738. [201] Co-editor Federico Echenique handled this manuscript. Manuscript received 1 July, 2019; final version accepted 19 January, 2020; available online 4 February, 2020.