1 Introduction↩︎

Network disruptions may have severe economic consequences for affected stakeholders [1] with firm-level shocks propagating into adverse macroeconomic outcomes [2]. Examples range from disaster-induced production losses [3] and reallocation externalities in project networks [4] to cascading bankruptcies through trade credit chains [5]. A common theme across these settings is that individual node fragility can escalate into systemic network fragility. The extent of such escalation depends on factors such as network configuration, diversification strategies, agents’ risk-mitigation decisions, and the structure of liability agreements [6]–[8]. As network efficiency is influenced by decentralized decisions [9], a central challenge is to align individual incentives with system-wide objectives. To address this challenge, we focus on the role of liability assignment in the context of cascading cancellations triggered by a disruptive event. Agents are connected in a directed acyclic network of, say, bilateral contracts in a supply chain. A shock forces the source node to cancel one of its contracts (e.g., a delivery); the agent affected by this cancellation must then cancel one of her own; and so on, until the process terminates at a final sink node (say, an end consumer). Each cancellation leads to an economic loss, which may vary with the agents involved. We do not impose any form of correlation between losses; for instance, low upstream losses may well be followed by much higher downstream losses. All losses are summarized in a loss function, which maps edges to losses. We take an axiomatic approach, designing a systematic procedure—a liability rule—to allocate the total path losses among the agents in the network. Such a rule is especially valuable as a rule-of-thumb for routine operations: rather than renegotiating liabilities following each disruption, agents commit upfront to a systematic liability scheme that can be applied immediately regardless of the canceled path and realization of losses.

Formally, each liability rule and loss function induces an extensive-form game of perfect information. Our first and central axiom, efficient implementation, asserts that the equilibrium outcomes of this game should coincide with the set of efficient paths. Second, realized-loss dependence centers on a practical feature: only on-path losses, which are inherently easier to verify and contract on than off-path counterfactuals, should matter. Third, pairwise collusion-proofness strengthens individual incentive compatibility by ruling out profitable joint deviations. No agent’s unilateral deviation should make any pair strictly better off, as this would enable side payments that undermine efficient implementation. Finally, we impose a standard regularity condition, scale invariance.

Theorem 1 shows that these four axioms jointly characterize the family of so-called fixed-weight rules. Such a rule is parameterized by a pre-set weight vector \(w\) and assigns to each agent \(i\) the fraction \(w_i \geq 0\) of the total loss with \(\sum_i w_i = 1\). Weights may depend on the network structure but not on the underlying loss function. For instance, weights will be positive for agents with multiple outgoing edges (this will be a consequence of efficient implementation). Fixed-weight rules are reductionist [10]: liabilities are assigned in the same way as if off-path losses were such that all paths are efficient, at which point there is no reason to condition liabilities on the chosen path. Yet more, the way losses are distributed along the chosen path is irrelevant: liabilities depend solely on the total path loss. In practice, it thus suffices to verify total losses along the canceled path and there is no need to distinguish some agent \(i\)’s individual loss from some other agent \(j\)’s; especially if losses for some reason are contentious, where it is not objectively clear which cancellation to associate them to, liabilities work the same and we do not need to take a stance. These rules are very robust and achieve the desired alignment of incentives even in more general settings.²

In this way, a central insight of our analysis is that losses should be treated as a common, systemic responsibility. Agents must internalize the full downstream consequences of their decisions. More local liability assignments are inadequate, e.g., in which the agent pays an amount increasing in the “direct” loss they cause to their successor (such as the ones introduced in [11] and [12]). Indeed, such rules may even generate unbounded inefficiency; see the example in Figure 1.³ This echoes the observation by [6], who note that “contracts whose terms are contingent only on individual outputs may be insufficient for dealing effectively with supply risk at higher tiers”. Even introducing solidarity among agents on the canceled path (e.g., sharing total losses equally among all on-path agents) generally fails to ensure efficient cancellations. Fixed-weight rules instead imply a broader notion of solidarity that extends beyond the realized path to off-path agents as well.

To single out one member of the class of fixed-weight rules, we suggest to set weights reflecting the fraction of source-sink paths that agents are part of. These weights possess a number of interesting features. For example, the source is always assigned the highest weight, which is counterbalanced by global solidarity in the sense that all agents (on- and off-path; decision and non-decision makers) have positive weights. Theorem 2 shows that these weights coincide with the Shapley value of a naturally associated cooperative game in which coalitional worth increases in path count.⁴ Further, the weights can be computed in polynomial time, ensuring that the approach remains tractable in larger instances as well.

We complement these findings with a simulation study, which highlights some advantages of this efficient rule over the natural status quo (namely, the “local-liability” rule in which each agent is liable only for the direct loss their choice causes). First, due to efficiency, average liabilities are lower and most agents are better off. Second, as our rule spreads liabilities thin but wide—many agents bear a small share rather than a few bearing the full burden—individual liability variation is significantly lower. Hence, in a richer framework with risk-averse agents, there are good reasons to believe that our approach may be advantageous to all parties.

Related literature. Our work relates to [17], who examine a similar setting of propagating network disruptions. They restrict to tree graphs in which agents have many incoming edges but only one outgoing, but, more importantly, their focus is different. Their disruptions follow a pre-specified propagation flow through the network and individual decisions pertain to investments made to avoid disruptions altogether. Whereas their incentive scheme influences the location and likelihood of disruption, in our work the disruption always occurs at the source and the liability rule instead affects the path selected (and, in turn, the total losses generated). In this way, our approach bears resemblance also to [11], who axiomatically study how to assign liabilities in a “post-disruption” setting (covering tree networks in which each node has at most one incoming edge). The current paper departs from this in that disruptions now have more limited consequences. Our affected agents need only cancel one outgoing edge, which adds a strategic dimension; in [11], a disruption leads by default to a complete failure of all downstream agreements. A related paper is [18], who study a bargaining game with asymmetric information between a retailer and an upstream supplier. They identify a cost-sharing contract that leads to efficient levels of investments for risk mitigation given certain probabilities of disruption (as represented by a specific parameterized functional form). This again differs from the approach taken in the current paper, as our model does not feature such investments.

Our paper also relates to the large literature on cost sharing in networks; see [19] for a recent overview. Typically, these models feature a central planner who seeks to implement an “efficient” network by eliciting information (e.g., on costs or demands) from agents and allocating network costs according to a cost-sharing rule.⁵ In comparison, our modeling framework is quite different. The “implemented network” (i.e., the canceled path) is determined by independent agent choices rather than a planner’s selection, we do not need to elicit any agent information, and a multiparty contract plays the role of the central planner in adjudicating liabilities.

Having said that, two papers relatively close to ours are [24] and [25]. In [24], agents have connection demands represented by pairs of nodes on an underlying graph, whereas the planner is ignorant about both connection costs and demands. Based on user reports, the planner estimates the efficient network and shares the realized costs according to a pre-announced cost-sharing rule. [24] use axioms similar to realized-loss dependence and efficient-path invariance (see our Proposition 2) to characterize so-called “linear simple rules”. They further examine conditions for which such rules induce truthful reporting in equilibrium. [25] consider sequential processes in which agents have individual values at each step (i.e., each edge creates a value for each agent). A planner selects what paths to implement and how to redistribute the accumulated aggregate value across agents. They characterize a class of rules (reminiscent of our fixed-weight rules) in a setting in which the planner has complete information. The focus of their analysis is on ex-post value sharing for given sequential outcomes, whereas our approach treats the allocation rule as an ex-ante incentive device designed to induce efficient path selection in a decentralized setting. They also explore an incomplete-information setting, in which the planner only is able to redistribute the realized individual values (agents, on the other hand, still have complete information) and agents vote on which path to implement. In this case, they primarily single out the “equal division” rule.

Outline. In Section 2, we introduce the model, liability rules, and the induced non-cooperative game. In Section 3, we present a number of desirable axioms, leading up to the characterization of the fixed-weight rules. In Section 4, we suggest how to set such fixed weights, which turns out to coincide with the Shapley value of an associated cooperative game. Section 5 presents the simulation study. Section 6 discusses two generalizations of the model. We conclude in Section 7. Proofs and technical details are postponed to the Appendix.

2 Model↩︎

In this section, we first introduce the primitives of the model. There is a fixed network representing agents and their bilateral relations (e.g., joint business projects). Associated to each project is an economic loss that would be incurred if the project was canceled. Moreover, cancellations cascade, forming a path through the network. In the end, losses get reassigned via a liability rule, which systematically allocates total cancellation losses to agents. Such a rule induces a non-cooperative game in which agents make strategic cancellation decisions with the objective of minimizing their own liability. From a systemic perspective, our aim is to identify liability rules for which the set of equilibria of the induced game coincides with the set of efficient cancellation paths.

2.1 Primitives↩︎

There is a directed graph \((N,E)\) that describes a network of at least three agents \(N\) and their relations \(E \subseteq N \times N\) (interchangeably, “nodes” and “edges”), which is held fixed throughout. We interpret the graph broadly to capture collaborative projects or input-output relations in a supply chain, where an edge \(ij \in E\) can be interpreted as agent \(i\) delivering inputs to agent \(j\). The graph is connected, acyclic in the directed sense, and has a unique source node \(s\) without incoming edges.⁶ Let \(i \to j\) whenever there is an edge \(ij \in E\). As the graph is acyclic, there is a topological (total) ordering \(\leq\) of \(N\) such that \(i \to j \implies i < j\) and there is at least one sink node without outgoing edges (e.g., representing end consumers). A path is a sequence of adjacent agents (or, interchangeably, adjacent edges) connecting the source to a sink. Let \(\mathcal{P}\) be the set of paths. Moreover, let \(N_P \subseteq N\) and \(E_P \subseteq E\) denote the nodes and edges, respectively, of path \(P\in {\cal P}\). Let \(\mathcal{P}^-_i\) be the set of subpaths (“histories”) from the source to agent \(i\) and \(\mathcal{P}^+_i\) be the subpaths (“continuations”) from agent \(i\) to a sink.

We impose a mild richness condition, namely that no interior agent can be part of all paths in \(\mathcal{P}\). An immediate implication is that the source has multiple outgoing edges.

The situation we consider is that the source \(s\) is hit by an exogenous shock. In consequence, the source has to select one of its outgoing edges to cancel; say \(s\) cancels \((s \to i_1)\). This has further repercussions: now agent \(i_1\) also has to cancel one of its edges, say \((i_1 \to i_2)\), and so forth. The cancellations continue to cascade to form a path connecting the source to a sink. Each edge \(e \in E\) has an associated loss \(\ell(e) \geq 0\) that is incurred if the edge is canceled. We think of the loss \(\ell(ij)\) as the costs incurred by agent \(j\) if agent \(i\) fails to deliver its inputs, but other interpretations are also possible. Let \(\ell \colon E \to \mathbb{R}_{\geq 0}\) describe the loss function and collect all such functions in \(\mathcal{L} \equiv \{ \ell \colon E \to \mathbb{R}_{\geq 0} \}\). For a path or subpath \(P\), define \(\ell(P) \equiv \sum_{e \in E_P} \ell(e)\) as the total loss of \(P\).

2.2 Efficient paths↩︎

Our primary objective is to incentivize efficient path cancellation. For this purpose, collect the cheapest, or efficient, paths in \[\textstyle \mathcal{E}(\ell) \equiv \arg \min_{P\in\mathcal{P}} \ell(P) \subseteq \mathcal{P}.\] Denote the cost of the cheapest \(i\)-to-sink subpath by \(L_i \equiv\min_{ P \in\mathcal{P}^+_i} \ell(P) \geq 0\) and the set of such subpaths by \[\textstyle \mathcal{E}_i(\ell) \equiv \arg \min_{P\in\mathcal{P}^+_i} \ell(P) \subseteq \mathcal{P}^+_i.\] The acyclic graph structure ensures that these costs and paths can be computed quickly, for instance using [26]’s ([26]) shortest path algorithm.

An immediate observation is that efficient paths are dynamically consistent [27]. That is to say, if we decompose an efficient path \(P\) into subpaths \(Q = (s \to \dots \to i)\) and \(R = (i \to \dots \to t)\) around an on-path agent \(i \in N_P\), then \(Q\) is a cheapest subpath from \(s\) to \(i\) and \(R\) a cheapest subpath from \(i\) to a sink \(t\).

2.3 Liability rules↩︎

In terms of timing, the network structure \((N,E)\) is fixed from the outset. Agents anticipate that disruptions may occur, but the nature and severity of the shock, and hence the induced loss function, may vary. Rather than renegotiating liabilities each time a disruption occurs, agents contract in advance on a liability rule, which systematically reassigns the incurred losses as a function of the canceled path \(P\) and the loss function \(\ell\). Such ex-ante contracting could for instance be implemented through blockchain-based smart contracts [11], [28]. Such a contract can automate liability assignment and reduce transaction costs, for instance those arising from legal disputes.⁷

Restricting to non-negative liabilities is a mild solidarity assumption: no agent should profit from disruptions if others are harmed. Balance is desirable to eliminate any need to inefficiently “burn” resources or to rely on subsidies from external parties. Once the shock occurs, the corresponding loss function is common knowledge. Hence, once agents choose edges to cancel, they do so knowing the graph, loss function, and liability rule. Although efficient paths thus are computable, they will only be realized if the liability rule correctly aligns individual incentives. Our objective is to design rules in such a way that the canceled path, jointly selected through independent choices, is efficient no matter the loss function. To formalize this, we next cast the interaction as a non-cooperative game.

2.4 The induced game and efficient implementation↩︎

Fix a rule \(\phi\) and loss function \(\ell \in \mathcal{L}\). The game induced by \(\phi\) and parameterized by \(\ell\) is denoted \(\mathcal{G}(\ell; \phi)\). This is an extensive-form game with perfect information. Its players are the agents \(N\). The source, agent \(s\), moves first and chooses its successor \(i\) among its neighbors \(N^+_s = \{ i \in N \mid s \to i \}\). Thereafter, \(i\) chooses its successor \(j\) from \(N^+_i = \{ j \in N \mid i \to j \}\), and so on. A strategy for an agent \(i\) is a function \(\sigma_i \colon \mathcal{P}^-_i \to N^+_i\), which assigns a successor \(\sigma_i(P) \in N^+_i\) to each history \(P \in \mathcal{P}^-_i\) leading up to \(i\). Let \(\sigma\) denote the strategy profile. Once we reach a sink, the game ends. Let \(\Pi(\sigma) \in \mathcal{P}\) denote the source-sink path realized under strategy profile \(\sigma\). Each agent \(j\) chooses strategy \(\sigma_j\) to minimize its liability \(\phi_j(\Pi(\sigma_j,\sigma_{-j}), \ell)\) with common knowledge on \(\phi\) and \(\ell\). We take subgame-perfect equilibrium as solution concept [29]. Let \(\mathcal{S}(\ell; \phi) \subseteq \mathcal{P}\) denote the set of paths that are subgame-perfect equilibrium outcomes of the game \(\mathcal{G}(\ell; \phi)\).

We wish to design the rule such that the set of paths realized under equilibrium play of the induced game coincide with the efficient paths [30].

There are many rules that satisfy efficient implementation. One example is equal division: share total losses equally among all agents. Indeed, this is a member of the class of rules that we will characterize and possesses a form of solidarity property in that losses are borne by all agents, not only the ones directly affected by the cancellations.

Having said that, efficient implementation can also be satisfied if losses are shared only along the canceled path. For instance, one can assign the full efficient cost \(L_s\) to the source and, for each on-path agent \(i\), assign liability equal to the difference between realized and efficient cost from \(i\) to the sink (that is, agents bear the systemic inefficiency associated to their choices). Although such a rule achieves efficiency, it relies on counterfactual losses and liabilities are sensitive to losses off the realized path. In what follows, we will argue against such rules due to practical concerns pertaining to enforceability, compliance, and stability. That is to say, it may be far easier to contract on realized losses than on counterfactual ones.

3 Axiomatic foundations↩︎

We introduce three additional desirable properties of rules: realized-loss dependence, pairwise collusion-proofness, and scale invariance. Our main axiomatic result, Theorem 1, shows that, together with efficient implementation, these properties characterize a class of rules that we term fixed-weight rules.

3.1 Realized-loss dependence↩︎

Recall that we interpret a liability rule as a contractual agreement between the agents. For this to be enforceable in practice, ideally the rule should depend only on verifiable outcomes; that is to say, whereas realized losses are observable ex post and can serve as the basis of enforceable transfers, counterfactual losses are inherently unverifiable and difficult to contract upon. In this spirit, our next axiom prohibits rules that depend on off-path losses. Such rules include, for instance, ones that hold agents liable for “the externalities they impose on others” by comparing realized losses with some counterfactual losses.⁸

We stress that this restriction on liability rules does not require abandoning efficiency. As we shall see, the axioms are compatible. Rather, realized-loss dependence plays the role among our axioms of ensuring that efficiency is achieved in a stable and practically feasible manner. We do not need complicated contracts based on counterfactual losses, it suffices to restrict attention to incentive schemes grounded in realized and verifiable losses.

Besides ensuring a practically viable rule, realized-loss dependence also adds a level of robustness to efficient implementation. First, an agent’s liability must increase in the total losses of the cheapest continuation following the agent’s choice, even off the equilibrium path. (As no inefficient subpaths are ever realized, liabilities of such paths do not need to be restricted.) We record this in Proposition 1, where \(\oplus\) is used to denote the operation of concatenating subpaths and edges.

An immediate implication of Proposition 1 is the following. Fix a rule \(\phi\) satisfying the two properties together with an arbitrary loss function \(\ell \in \mathcal{L}\) and equilibrium strategy profile \(\sigma \in \mathcal{S}(\ell; \phi)\). Then, for each agent \(i\) and history \(P \in \mathcal{P}^-_i\), \[\textstyle \sigma_i (P) \in \arg \min_{j \in N^+_i} \left ( \ell(ij) + L_j \right ).\] That is to say, not only do agents make efficient decisions in equilibrium, but the same extends even off the equilibrium path. We denote this property robust efficient implementation. We remark also that robust efficient implementation is a genuine strengthening of efficient implementation: there are rules that satisfy the latter but not the former.⁹

3.2 Pairwise collusion-proofness↩︎

Whereas efficient implementation addresses individual incentives, our next axiom pertains to group collusion. Take an equilibrium path \(P\) and a pair of agents \(i\) and \(j\). It should then not be the case that a strategic deviation by \(i\) makes the pair jointly improve. If such a deviation was beneficial, then \(i\) and \(j\) could arrange side payments to make them both better off.

We next find that, when taken together, efficient implementation and pairwise collusion-proofness imply that when multiple efficient paths exist, then it makes no difference which we select. This is in itself desirable to circumvent any form of potential conflicts between agents on which efficient path to target. Restated in the language of implementation theory, the problem can be viewed as associating to each loss function a set of outcomes (here the efficient paths); the axioms then imply that the corresponding social choice correspondence is essentially single-valued [31], [32].

The proof is straightforward. Take two distinct efficient paths \(P\) and \(P'\), so \(\ell(P) = \ell(P')\), and let \(i\) be the first agent to make different choices under the two. Any strict preference for \(i\) between the two paths would rule out one as an equilibrium outcome, contradicting efficient implementation. Moreover, any strict preference for some agent \(j \neq i\) between the two would allow \(i\) and \(j\) to collude, contradicting pairwise collusion-proofness. Hence, liabilities must be the same for the two paths.

Next, Proposition 3 shows that rules satisfying our basic principles—the fundamental efficiency-incentive alignment of efficient implementation, the informational constraint of realized-loss dependence, and the stability property of pairwise collusion-proofness—must be redistribution invariant. That is to say, although liabilities \(\phi(P,\cdot)\) can depend on total losses \(\ell(P)\), they cannot depend on where each loss is incurred along the edges of \(P\).

The proof of Proposition 3 is a bit more involved. We decompose the redistribution from \(\ell\) to \(\ell'\) into a sequence \(\ell, \ell^1, \ell^2, \dots, \ell'\) of local adjustments that preserve the total loss on the path. In each step, the respective loss function is designed to keep the relevant paths efficient and leave realized losses unchanged for suitably chosen comparison paths. Efficient-path invariance (Proposition 2) ensures that liabilities are equal across paths at each step, whereas realized-loss dependence carries the argument across steps. By iterating this reasoning, we find that redistributing losses along a path will not affect liabilities.

Next, Proposition 4 offers a complementary finding: the rules satisfying our desirable axioms must also be path independent. That is to say, liabilities \(\phi(\cdot,\ell)\) cannot depend on which of the equally-costly paths was chosen.

To sketch the argument, we go via an alternative loss function \(\hat{\ell}\) that leaves losses on \(P\) unchanged while rendering all paths efficient. Under \(\hat{\ell}\), both \(P\) and \(P'\) are efficient and, by efficient-path invariance (Proposition 2), liabilities are equal. Since \(\hat{\ell}\) coincides with \(\ell\) on \(P\), realized-loss dependence implies that liabilities on \(P\) are unchanged. Moreover, as \(P\) and \(P'\) have the same total loss under both loss functions, \(\hat{\ell}\) differs from \(\ell\) along \(P'\) only by a redistribution; by Proposition 3, liabilities are again equal. Taken together, this yields \(\phi(P, \ell) = \phi(P', \ell)\).

An immediate consequence of Propositions 3 and 4 is that liabilities should depend only on the path’s total losses.

3.3 Scale invariance and the class of fixed-weight rules↩︎

The final axiom is the conventional assumption that large and small problems are solved alike; that is, the rule is scale invariant. Scaling all losses by a common factor scales liabilities accordingly.

As noted in Corollary 2, efficient implementation, realized-loss dependence, and pairwise collusion-proofness imply that liabilities should depend only on the path’s total losses. With the additional requirements of scale invariance, we can pin down a parameterized family of rules. For this purpose, let first \(\Delta^N = \{ w \in \mathbb{R}^N_{\geq 0} \mid \sum_i w_i = 1\}\) denote the usual \(N\)-simplex. We associate to each point \(w \in \Delta^N\) a rule that always shares total losses in proportion to the weights \(w\).

In a sense, a fixed-weight rule simplifies the design problem from determining how losses should be assigned in each contingency to determining how total losses should be weighted across agents as a function of the network structure. That is, weights can be conditioned on graph-based primitives and normative considerations; thereafter, liabilities scale accordingly. Standard examples include equal division (\(w_i = w_j\) for all agents \(i\) and \(j\)), weights proportional to the number of paths that agents are on or to source distance, as well as any form of node centrality measure [19], [33].

It is not difficult to see that fixed-weight rules satisfy realized-loss dependence, pairwise collusion-proofness, and scale invariance. To ensure efficient implementation, we need to impose one additional restriction on weights. As agents with multiple outgoing edges need to be incentivized to make efficient choices (and there are loss functions under which it is critical that they do), they must be assigned positive weight.¹⁰ Therefore, let \[\Delta^N_\star = \{ w \in \Delta^N \mid w_i > 0 \text{ for agents i \in N with \lvert N^+_i \rvert > 1} \}.\] We are now ready to state our main axiomatic result. Independence of the axioms is shown in Appendix 9.

The result of Theorem 1 highlights a surprising implication: agents who can make choices must bear a positive share of every realized loss—even those arising on paths that completely bypass the agent and for which the agent’s choices are irrelevant. At its extreme, consider Figure 2, in which dashed edges have zero losses and solid edges have positive losses. Even though total losses stem from the source’s choice whereas agent \(j\)’s choice adds no additional harm, we will still have that \(j\) is assigned positive liability; for instance, we will have \(\phi_j(P,\ell) > 0\) for path \(P = (s \to i \to t)\). Put differently, agent \(j\) bears a higher cost than the total losses of the subgraph from \(j\) and on, \(\ell(jk) + \ell(jt) = 0\).

Fixed-weight rules not only incentivize efficient implementation at the individual level, but even at the group level. That is to say, if a group \(S \subseteq N\) attempted to “collude” and coordinate their decisions, then they would still jointly pay \(\sum_{i \in S} \phi_i(P,\ell) = \sum_{i \in S} w_i \cdot \ell(P)\). Hence, they can do no better than minimizing \(\ell(P)\) by choosing an efficient path. In this way, pairwise collusion-proofness joint with our other axioms imply a stronger form of “full” collusion-proofness. (This is reminiscent of properties such as group strategy-proofness, see e.g. [34].) Further robustness arguments in favor of fixed-weight rules are discussed in Section 6.

4 Choosing weights↩︎

In this section, we single out a particular method of setting weights. The underlying principle is that agents appearing on many potential cancellation paths, especially shorter ones, should receive higher weight. Hence, a natural approach is to proceed path by path and assign weights reflecting the frequency and importance of an agent’s presence across paths. This parallels ideas in cooperative game theory that more “pivotal” agents receive higher shares, for example as in the [13] ([13]) value. Indeed, we will find that the weights \(w^*\) to be introduced next coincide with the Shapley value of a naturally associated cooperative game. In contrast to the general case in which the value may be computationally intractable [35], our model allows a convenient shortcut to quickly compute such Shapley-like weights \(w^*\) even for large problems.

We assume that sinks \(t\) are assigned zero weight. This mirrors the logic of strict liability (that an injurer is responsible for the losses she causes) from the literature on law and economics [36]. Here, in particular, sinks incur losses but cause none, so we take as given that they are free of liability [11]. With this in mind, it will turn out to be convenient to work with the set of non-sink agents. We denote them \(N^* \equiv \{ i \in N \mid N^+_i \neq \emptyset \} \subset N\) and, analogously, let \(N^*_P \equiv N_P \cap N^*\) be the non-sink agents of path \(P\).

4.1 Path-by-path algorithm↩︎

We introduce first a simple algorithm to compute the weights \(w^* \in \Delta^N_{\star}\). We proceed path by path. Let \(\lvert \mathcal{P} \rvert\) denote the number of paths. All agents on a path are treated the same; a value of \(1 / \lvert\mathcal{P}\rvert\) is shared between all non-sink agents on the path. Thereafter, we sum these values over all paths. As each agent is part of at least one path, all non-sink weights are positive.

Applied to the case of a tiered supply-chain network (with nodes representing suppliers, manufacturers, retailers etc. and sinks corresponding to end consumers), these weights may admit an even simpler interpretation. Specifically, assume that edges link each layer only to the next one, and does so in a “symmetric” way: all nodes in a given layer have the same number of outgoing edges and the same number of incoming edges. In this case, \(w^*\) is computed by double application of equal division: first total losses are shared equally across layers, and then equally among nodes within each layer.¹¹ Hence, liabilities are highest in “thin” layers (e.g., bottleneck-like central distribution nodes).

4.2 Relation to the Shapley value↩︎

We continue our analysis of the fixed-weight rule with weights \(w^*\) by highlighting a connection to cooperative game theory [37]. Define the path-counting game \(v\) with players \(N^*\) (i.e., non-sink agents) as follows. For every coalition \(S \subseteq N^*\), let the worth \(v(S) \in [0,1]\) be the fraction of all paths that only cover nodes in \(S\): \[v(S) = \frac{\lvert\{ P \in \mathcal{P} \mid N^*_P \subseteq S \} \rvert}{\lvert\mathcal{P}\rvert}.\] For instance, if \(s \to i \to t\) denotes a path, then this is counted for all coalitions \(S\) with \(\{ s, i \} \subseteq S\). As all paths include the source, coalitions \(S\) that do not include the source \(s\) have zero values. For the (grand) coalition of non-sink agents, we have \(v(N^*) = 1\).

Theorem 2 shows that the weights \(w^*\) coincide with the Shapley value of \(v\). To build intuition, associate to each path \(P \in \mathcal{P}\) the simple game \(v^P\) with \(v^P(S) = 1\) if \(N^*_P \subseteq S\) and \(v^P(S) = 0\) otherwise. The path-counting game \(v\) is a linear combination of these simple games \(v^P\). As the Shapley value is linear [13], it follows that the Shapley value of \(v\) is obtained by summing the Shapley values of the simple games, which yields \(w^*\).

If adding \(i\) to coalition \(S\) completes path \(P\), then adding \(i\) to a larger coalition \(T \supseteq S\) also completes \(P\). Hence, if \(S \subseteq T\), then \(v(S \cup \{i\}) - v(S) \leq v(T \cup \{i\}) - v(T)\). That is to say, the path-counting game \(v\) is convex and, therefore, the Shapley value is in the game’s core [38]. Although core stability is not central to our application, we can interpret this as that no coalition is unfairly treated: no coalition is allocated less weight than the share of paths it realizes on its own.

4.3 Polynomial-time computation↩︎

An obstacle to using the Shapley value in practical applications is that exact computation quickly gets intractable. To compute \(i\)’s contribution to every coalition, the number of steps rapidly grows prohibitively large; already with \(n = 30\) agents, there are \(2^{30} \approx 10^9\) coalitions. In a sufficiently sparse graph with few paths, the algorithm in Subsection 4.1 may be tractable even if there are many nodes. However, it too can run into a similar worst-case scenario. The number of paths may grow exponentially with the number of agents so iterating over all paths may, again, be slow. Figure 3 gives an example of a grid-like graph with \(2m + 2\) nodes and \(2^m\) paths. With \(n \approx 60\) agents, we may have a billion paths to sum over.

The key to ensure scalable, fast computation is to note that agent \(i\) is attributed the same amount for each five-agent path no matter who the other four agents are. For this reason, it suffices to find the distribution of the agent’s paths (how many of length \(1\), length \(2\), and so on) and one does not need to track all paths. This then becomes a simple exercise in dynamic programming. We exploit the topological order to make two passes: one forward to compute subpaths from the source, and one backwards to compute continuations to the sinks. Intuitively, if there are two subpaths from the source to agent \(i\) of length \(1\) and \(2\) and two subpaths of length \(3\) and \(4\) from \(i\) to the sinks, then \(i\) is part of four source-sink paths: one of length \(1 + 3\), two of length \(1 + 4 = 2 + 3\), and one of length \(2 + 4\).

Let \(n = \lvert N \rvert\) denote the number of nodes. Let \(F(x, j) \in \mathbb{Z}\) denote the number of subpaths of length \(x \in \{0, \dots, n\}\) from the source to agent \(j\). This is computed as follows. Begin by setting \(F(0, s) = 1\) to capture the trivial subpath from the source to itself. Moreover, set \(F(x, s) = 0\) for positive lengths \(x > 0\) and \(F(0,j) = 0\) for all non-source nodes \(j \neq s\). Proceed in topological order, starting with nodes that have incoming links only from the source. For each agent \(j\) and length \(x \in \{0, \dots, n\}\), let \(N^-_j \equiv \{ i \in N \mid i \to j \}\) and set \[F(x+1, j) = \sum_{i \in N^-_j} F(x, i).\] Intuitively, for each subpath that reaches \(i\) in \(x\) steps, we concatenate the edge \(i \to j\) and obtain one subpath that reaches \(j\) in \(x+1\) steps. In total, \(F\) is computed by evaluating roughly \(n^2\) sums.

Thereafter, we do an analogous backward pass: let \(B(x, i) \in \mathbb{Z}\) denote the number of subpaths of length \(x \in \{0, \dots, n\}\) from agent \(i\) to some sink. This time, for each sink \(t\), set \(B(0, t) = 1\), \(B(x, t) = 0\) for \(x > 0\), and \(B(0,i) = 0\) for non-sink nodes \(i\in N^*\). Proceed instead from the end in reverse topological order; in general, set \[B(x+1, i) = \sum_{j \in N^+_i} B(x, j).\]

Let \(P(y, i) \in \mathbb{Z}\) denote the number of source-sink paths of length \(y \in \{1, \dots, n\}\) that agent \(i\) is part of. This can be computed through the convolution \[P(y, i) = \sum_{x = 1}^y F(x,i) \cdot B(y-x,i).\] (Strictly speaking, there are \(x\) agents before \(i\) and \(y-x\) agents after \(i\), out of which one is a sink; hence, once we include \(i\) in the path and exclude the sink, we indeed have \(y\) non-sink agents on the path.) This is a sum of roughly \(n\) multiplications.¹² Finally, we have \[w^*_i = \frac{1}{\lvert{\mathcal{P}\rvert}} \sum_{y = 1}^n P(y, i) / y.\]

5 Simulation study↩︎

To gain further insights on our fixed-weight solution \(\phi^*\), we compare it numerically to the simple benchmark in which each agent is liable only for the loss they directly cause to their successor. This is the natural status quo in the absence of coordination via a common contract: \[\widehat\phi_i(P,\ell) = \begin{cases} \ell(ij) & \text{if } ij \in E_P \\ 0 & \text{otherwise.} \end{cases}\]

We construct a tiered supply-chain network with five production layers and a sixth consumer layer. Links are mainly from one layer to the next, but we also allow “shortcuts” that skip one layer. The network has an “hourglass” structure with many suppliers feeding into a smaller set of intermediaries before distributing to a larger set of consumers. Specifically, the six-layer network has 30, 20, 15, 10, 15, and 20 nodes per layer and its edges are randomly generated. For each pair of nodes in layers \(\ell\) and \(\ell + 1\), there is a link with probability \(40\%\); for nodes in layers \(\ell\) and \(\ell + 2\), there is a link with probability \(10\%\). Sinks are in the consumer layer only, and each sink is reachable from some source (base-layer) node.

Although the graph no longer has a unique source node, extending \(\phi^*\) to this case is straightforward. We treat each of the 30 base-layer nodes as a source, one at a time. For a given source, we identify the subgraph reachable from this node and apply our path-counting algorithm on this subgraph. We then draw a loss function at random (independently and uniformly from \(0\) to \(100\) for each edge). We compute the efficient cost, our fixed-weight solution \(\phi^*\), and the “local-liability” rule \(\widehat\phi\). This is repeated for \(10\,000\) randomly generated loss functions before proceeding to the next source node. Liabilities are averaged over all \(30 \cdot 10\,000\) instances. The data is summarized in Table 1.

Given that the network is relatively small and the losses are randomly generated, we focus on qualitative insights. First, as expected, the efficient liabilities under \(\phi^*\) do better in terms of total losses incurred; our results suggests that \(\widehat\phi\) would increase total losses by about \(50\%\). This is partly explained by \(\phi^*\) inducing slightly shorter paths (by taking more shortcuts): the average path length is roughly \(10\%\) longer under the alternative rule. Looking at the distribution across agents, we find that \(\phi^*\) generates a more equal liability profile (as measured by the Gini coefficient), consistent with the idea that fixed weights encode a form of solidarity. If we instead look at the average squared liability, every agent is better off under our fixed-weight solution. This points to an insurance-like aspect of the rule: each agent always pays a little; for contrast, liabilities exhibit much larger variation under the local-liability rule.

Still, not all agents are better off. Out of the 90 non-sink agents, 74 are better off under \(\phi^*\). Intuitively, a central distribution center with many outgoing edges will be part of many paths and therefore be assigned a high weight under our rule. By contrast, under \(\widehat\phi\), more outgoing edges is beneficial: the agent only covers the loss of the canceled edge, and this can be done cheaply if there are many options. A simple way to illustrate the difference is to fix the node’s total degree (that is, sum of in- and out-degree). Under \(\widehat\phi\), liability increases in in-degree and decreases in out-degree; under our fixed-weight solution \(\phi^*\), liability instead increases most strongly in the product of in- and out-degree.

6 Discussion↩︎

We briefly sketch two natural generalizations. In both cases, the main insights from our analysis remain intact under the broader modeling framework.

6.1 Incomplete information on losses↩︎

In our model, the loss function is common knowledge. In practice, this assumption may be restrictive. For instance, agent relationships may be governed by bilateral contracts under which each agent knows only the losses associated with their own contracts (edges). Nevertheless, our results are robust under this more realistic specification of incomplete information. To see this, suppose that the loss on edge \(ij\) is private information known only to agents \(i\) and \(j\). Consider the following two-stage procedure. First, all agents report losses for the edges they know. Subsequently, agents make cancellation choices as in Section 2 but with information on the reported losses instead. Under a fixed-weight rule, reports will be truthful: no agent can gain from misreporting edge losses, as doing so can only distort others’ efficient decisions and increase total losses and, in turn, the agent’s own liability.

In similar spirit to how smart contracts can implement the liability rule, they can be extended to make this two-stage procedure operational as well. That is, the contract would act as a coordination device that collects reports, registers agent actions, and assigns liability; see, for instance, [11] for a sketch of such a setup.

6.2 Generalized cancellation games↩︎

Fixed-weight rules are very robust and ensure efficient implementation in general. To illustrate, consider the following sequential-move game. We maintain the assumption of a directed acyclic graph \((N,E)\) with a unique source \(s\) but allow for more general forms of cancellation structures:

1. The source \(s\) chooses an action \(a_s\) from a given set of actions \(A_s\). So far, \(A_s\) has been the agents adjacent to the source; now, it can be far more general. For instance, an action could represent a subset of adjacent agents (in case \(s\) has to cancel multiple edges) or combine an edge with a “degree of cancellation” (e.g., capturing a partial breakdown), and more. The choice \(a_s\) determines the next agent, \(i_1 = f(a_s) > s\) (hence, even if the choice represents multiple affected agents, we still proceed sequentially).

2. Agent \(i_1\) chooses an action \(a_1\) from some action set \(A_1(a_s)\). The available actions may depend on the source’s choice: for instance, if \(a_s, a'_s \in A_s\) capture different cancellations decisions, then we may have \(A_1(a_s) \neq A_1(a'_s)\) even if \(f(a_s) = f(a'_s)\). Jointly, the choices \(a_s, a_1\) determine the next agent, \(i_2 = f(a_s, a_1) > i_1\).

4. In general, agent \(i_k\) chooses an action \(a_k\) from some action set \(A_k(a_s, \dots, a_{k-1})\). All choices up to this point determine the next agent, \(i_{k+1} = f(a_s, a_1, \dots, a_k) > i_k\).

As there is a finite number of agents, the game ends in a finite number of steps. The non-negative total losses generated through this realization of the game is a function of all choices \(a_s, a_1, \dots, a_t\). As long as these losses are shared according to a fixed-weight rule, equilibrium choices will be efficient (redefined to fit the new game structure).

7 Concluding remarks↩︎

We have studied liability assignment on networks where agents’ actions jointly determine both efficiency and loss allocation. Our axiomatic analysis has singled out the class of fixed-weight rules, which achieve efficient implementation using balanced, scale-invariant transfers that ensure consistent liability across efficient outcomes. We propose a particular fixed-weight rule, justified in part by its connection to cooperative game theory. Specifically, the associated weights result from application of the Shapley value to a related cooperative game. In this regard, we have emphasized the computational features that are specific to our particular model. Finally, we have argued that fixed-weight rules in general are robust; even in broader domains, they can be used to implement efficient outcomes via simple coordination devices. This suggests that fixed-weight rules provide a tractable and transparent approach to allocating responsibility for cascading network failures.

References↩︎

---

1. We thank Jay Sethuraman and Lars Peter Østerdal for valuable comments. Financial support from the Independent Research Fund Denmark (grant no. 4260-00050B) is gratefully acknowledged.↩︎

2. In Section 6, we briefly discuss allowing for incomplete information on losses and extending to more general action sets of the agents such as fractional and multi-contract cancellations.↩︎

3. In Appendix 10, we provide a complementary impossibility result. Specifically, there are graphs for which no rule satisfies efficient implementation, realized-loss dependence, and “on-path only” liabilities.↩︎

4. The axiomatic foundations for the Shapley value are well understood; see, for instance, [13]–[16].↩︎

5. In [20], the planner elicits connection demands from network users and builds the cheapest network meeting all demands (knowing connection costs). [21] and [22] focus on an edge-specific rule that splits costs equally between users. They examine the induced cost sharing game in which users’ strategies consist of paths satisfying their connection demand and study worst-case performance in equilibrium. [23] consider implementation using cost-sharing rules restricted to depend only on individual path costs and total network cost.↩︎

6. It is straightforward to extend to a network with multiple nodes without incoming edges as long as we maintain the assumption that only one is directly affected by the shock; compare Section 5. Agents who cannot be affected even indirectly (i.e., nodes not reachable from the shock) are then considered free of liability.↩︎

7. The case in which the liability rule also is contingent on the location of the shock is discussed in Section 5.↩︎

8. This property resembles the axiom “Unobserved information independence” in [24]. Somewhat similar ideas have been considered in [22] and [23] creating minimum information frameworks for implementation of efficient connection networks.↩︎

9. For instance, let the rule \(\phi\) “punish” the first agent to make an inefficient choice. If \(P \in \mathcal{E}(\ell)\), then share losses equally: \(\phi_i(P,\ell) = 1/n \cdot \ell(P)\); otherwise, for \(P' \not \in \mathcal{E}(\ell)\), there is a first agent \(i\) to make an inefficient choice (that is, all paths resulting from \(i\)’s choice are inefficient). In this case, assign full liability to \(i\): \(\phi_i(P',\ell) = \ell(P')\). This rule satisfies efficient implementation, but off the equilibrium path agents are free of liability and efficient continuations are not guaranteed. Hence, it fails robust efficient implementation.↩︎

10. To see why, take as example \(w \in \Delta^N\) with \(w_s = 0\): that is to say, suppose that the source is free of liability. Hence, we always have \(\phi_s(P,\ell) = 0\), so the source is indifferent between all paths—including inefficient ones. Then there can be inefficient equilibria, contradicting efficient implementation. To extend the conclusion to any agent \(i\) with multiple outgoing edges, we apply the argument for the particular case in which the loss function \(\ell\) is such that \(i\) is part of at least one efficient and one inefficient path.↩︎

11. In this case, all paths are of the same length and include one node from each layer. As agents within a layer have the same in- and out-degrees, they are part of the same number of paths.↩︎

12. For large graphs, the process may be sped up through a fast Fourier transformation [39]. As a benchmark, computing \(w^*\) on a normal laptop for a graph with \(n = 1\,000\) nodes and \(10^{17}\) paths takes roughly one second. This would be intractable with the procedures in Subsections 4.1 and 4.2.↩︎