Chapter 9 Exchange Networks

In this chapter, we will consider a generalized form of matching markets, referred to as exchange networks. Roughly speaking, rather than just considering bipartite graphs where the left nodes are buyers and the right nodes are items/sellers, we will now consider exchanges over arbitrary networks. We first describe the problem and then relate it back to matching markets.

9.1 Definition of an Exchange Network

Assume we have an undirected graph $G = (V, E)$ with $n$ nodes; the nodes in this graph represent the players, and an edge between two players means that the players may perform “an exchange” with each other. Each edge $e$ is associated with some amount $v (e)$ that can be split between its endpoints if an exchange between the endpoints takes place—think of this value as the value of a potential partnership between the endpoints. Nodes can participate in at most one exchange (i.e., they form exclusive partnerships); in other words, the partnerships form a matching in $G$ . The outcome of such an exchange network is thus a matching in $G$ , and assignments of values to players representing the players’ share of the value of the partnership they (potentially) participate in:

Definition 9.1. An exchange network is a pair $(G, v)$ , where $G = (V, E)$ is a graph and $v : E \to ℕ$ is a function. An outcome of an exchange network $(G, v)$ is a pair $(M, d)$ where:

M

is a matching in

G

(i.e., a subset of

E

where no two edges share a common endpoint).

$d : V \to ℕ$ is a “division” (or split) of amounts to nodes such that for every $e = (x, y) \in M$ , $d (x) + d (y) = v (e)$ , and for every node $x$ not part of an edge in $M$ (i.e., $M (x) = ⊥$ ), $d (x) = 0$ . (That is, for every edge $(x, y)$ , the amount $v (x, y)$ gets divided between $x$ and $y$ .)

To see how this notion captures a matching market, consider a bipartite $G$ —the “left nodes” correspond to buyers and the “right nodes” correspond to the items; the value of an edge $e$ between a buyer $i$ and an item $y$ is simply the value $v$ player $i$ has for the item $y$ . The exclusive partnership condition here models the fact that players only get at most one item, and each item $y$ can only be sold to a single player. When the price $p$ for an item $y$ has been set, and the item gets sold to some buyer $i$ , player $i$ ’s value $v$ for item $y$ , gets split between $i$ and the seller— $p$ gets allocated to the seller and $v - p$ gets allocated to the buyer $i$ .

But exchange networks can capture significantly more general strategic interactions, even if $G$ is bipartite—we no longer need to view the nodes as “buyers” and “items/sellers,” but rather just as individuals in a social network that engage in some form of exclusive partnerships. In particular, we can now see how some nodes in the social network are “more powerful” than others (due to the network structure), in the sense that they will get a “better deal” in the partnerships they establish. Indeed, such interactions have been empirically studied in the sociological field of “network exchange theory” [Wil99].

To do this, we first need to have a way to generalize the notion of a market equilibrium to exchange networks. The notion of a stable outcome does this.

9.2 Stable Outcomes

We call an outcome $(M, d)$ stable if no node $x$ can improve its allocated amount by establishing a new partnership with some node $y$ such that (a) $x$ is strictly better off with $y$ than in its current allocation, and (b) $y$ receives at least as much as it does in its current allocation. Intuitively, if such a pair of nodes $(x, y)$ exists (i.e., the outcome is unstable), then we would expect $x$ to break its current partnership and propose a new partnership to $y$ which $y$ would accept.¹ A mathematically cleaner way of saying the same thing is to require that for every pair of nodes $(x, y)$ , their currently allocated combined amount, $d (x) + d (y)$ , is at least as large as the value of their potential partnership, $v (x, y)$ : if $d (x) + d (y) < v (x, y)$ , then $x$ and $y$ can, for instance, form a new partnership with the division $d^{'} (x) = d (x) + s / 2$ and $a^{'} (y) = d (y) + s / 2$ (one of them rounded upward and the other downward), where $s = v (x, y) - d (x) - d (y)$ is the surplus on the $(x, y)$ edge. Since the surplus is positive, at least one of them will be better off and the other at least as well off.

Definition 9.2. Given an exchange network $(G, v)$ , we call an outcome $(M, d)$ unstable if there exists a pair of nodes $x, y$ in $G$ such that $(x, y) \notin M$ , but $d (x) + d (y) < v (x, y)$ (i.e., the edge has a positive surplus). If $(M, d)$ is not unstable, we call it stable.

In other words, an outcome is stable if and only if all edges have a surplus of 0. Let us now show that this notion indeed generalizes that of a market equilibrium. First, we need to formalize the correspondence between matching markets and exchange networks:

Given a matching market $Γ = (n, Y, \vec{v})$ , we say that $(G, v^{'})$ is the exchange network corresponding to $Γ$ if (a) $G$ is the complete bipartite graph over $[n] \cup Y$ , and (b) $v^{'} (i, y) = v_{i} (y)$ .
Given an exchange network $(G, v^{'})$ where $G = ([n] \cup Y, E)$ is a bipartite graph, we say that $Γ = (n, Y, \vec{v})$ is the matching market corresponding to $(G, v^{'})$ where $v_{i} (y) = 0$ if $(i, y) \notin E$ , and $v_{i} (y) = v^{'} (i, y)$ otherwise.

We now have the following claim.

Claim 9.1. Let $Γ = (n, Y, \vec{v})$ be a matching market and let $(G, v)$ be the exchange network corresponding to $Γ$ . Or, conversely, let $(G, v)$ be an exchange network where $G = ([n] \cup Y, E)$ is bipartite, and let $Γ$ be the matching market corresponding to it. Consider any prices $p : Y \to ℕ$ , any matching $M$ in $G$ , and any division function $d : V \to ℕ$ such that:

$d (y) = p (y)$ if $y \in Y$ ;
$d (i) = v_{i} (M (i)) - p (M (i))$ if $i \in [n]$ and $M (i) \neq ⊥$ ;
$d (i) = 0$ otherwise.

Then $(M, p)$ is a market equilibrium in $Γ$ if and only if $(M, d)$ is a stable outcome in $(G, v)$ .

Proof. We separately prove each direction.

The “only-if” direction: Assume for contradiction that $(M, p)$ is a market equilibrium in $Γ$ , but $(M, d)$ is not stable in $(G, v^{'})$ —that is, there exists some unmatched buyer–item pair $(i, y)$ such that $d (i) + d (y) < v (i, y)$ . By our construction of $d$ , this means that

v_{i} (M (i)) - p (M (i)) + p (y) < v_{i} (y) .

Thus, $v_{i} (M (i)) - p (M (i)) < v_{i} (y) - p (y)$ , which means that $i$ would strictly prefer to buy item $y$ at its current price (to buying item $M (i)$ that it currently is getting), which contradicts the market equilibrium property of $(M, p)$ .

The “if” direction: Conversely, assume for contradiction that $(M, d)$ is stable in $(G, v^{'})$ , but $(M, p)$ is not a market equilibrium in $Γ$ —that is, there exists some buyer $i$ who prefers buying item $y$ at price $p (y)$ to the item (or lack thereof) $M (i)$ to which they currently are assigned. Assume first that $i$ is matched to some object $M (i) \neq ⊥$ . Then, we have that

v_{i} (M (i)) - p (M (i)) < v_{i} (y) - p (y) .

By the definition of $a$ and $v^{'}$ , the left-hand side equals $d (i)$ and the right-hand side equals $v^{'} (i, y) - d (y)$ ; thus, we have

d (i) < v^{'} (i, y) - d (y),

which contradicts the stability property of $(M, d)$ . Consider, finally, the case that is $M (i) = ⊥$ . Then $d (i) = 0$ , but, since $i$ prefers to buy $y$ , $v_{i} (y) > p (y) = d (y)$ . So

d (i) + d (y) = d (y) < v_{i} (y) = v (i, y),

which, again, contradicts the stability property of $(M, d)$ .

■

Let us point out that, a priori, there is a surprising aspect of Claim 9.1: the notion of a market equilibrium only says that no buyer wishes to switch to some other item—it does not impose any restrictions on the item/seller not wanting to switch to some other buyer (who may be willing to pay more)—yet the notion of stability (when considering the exchange network corresponding to a matching market) treats buyers and sellers symmetrically and requires that neither of them prefer switching to some other partnership. So, why are we getting this “no-deviation” property also for sellers (for free)? The point is that if a seller $y$ could propose a partnership to buyer $i$ that is better for $y$ , that means there is a surplus on the $(i, y)$ edge, which in turn means that $i$ can also propose a partnership to $y$ that $i$ prefers to its current deal (i.e., there indeed exists some buyer $i$ who prefers to switch to some object $y$ that they currently are not matched with).

9.3 Existence of Stable Outcomes

A direct application of Claim 9.1, combined with Theorem 8.2 (which states that market equilibria always exist in a matching market), gives an existence theorem for stable outcomes in bipartite graphs.

Theorem 9.1. Any exchange network $(G, v)$ where $G$ is bipartite has a stable outcome. Furthermore, such a stable outcome can be found in polynomial time in the size of $G$ and the maximum value of any edge in the graph.

Proof. Observe that the notion of stability does not depend on the names/labels of the nodes in the graph, so we may without loss of generality assume that set of “left nodes” in the bipartite graph $G$ are $[n]$ . By Claim 9.1, a stable outcome in $(G, v)$ exists if and only if there exists a market equilibrium in the matching market $Γ$ corresponding to $(G, v)$ ; by Theorem 8.2 such equilibria always exists.

■

A natural question is whether stable outcomes exist in all (and not just bipartite) graphs. The answer turns out to be no, even for very simple graphs.

Claim 9.2. There exists an exchange network with three nodes for which no stable outcome can exist.

Proof. Consider a “triangle” $G$ with three nodes (i.e., all nodes are connected by an edge), and for every edge $e$ , set the value of the edge, $v (e)$ to some integer $k \geq 2$ . Assume, for contradiction, that we have a stable outcome $(M, d)$ in $G$ . Since $G$ is a triangle, any matching in $G$ can contain at most one edge. If $M$ contains no edges, $d (x) = 0$ for every node $x$ , and thus for any pair of edges $(x, y)$ , $d (x) + d (y) = 0 < v (x, y) = k$ , so $(M, d)$ is not stable. Consider next the case when $M$ contains one edge $(x, y)$ . One of the nodes, say $x$ , must have $d (x) \leq \frac{k}{2}$ , and the third node $z$ must have $d (z) = 0$ (since it is unmatched); thus, $d (x) + d (z) \leq \frac{k}{2} < k$ , which means the outcome is not stable.

■

Note that the triangle example shows that any outcome, in fact, must have some edge $(x, z)$ with surplus at least $\frac{k}{2}$ . So, if $x, z$ split the surplus evenly (i.e., $x$ offers himself $3 k / 4$ and offers $k / 4$ to $z$ ), both players gain at least $k / 4$ by forming this new partnership. This example thus rules out even more relaxed notions of stability where a deviation is only deemed viable if both players are substantially better off than in their current allocation.

9.4 Applications of Stability

Let us now turn to applying the notion of stability to some example graphs. (All of these graphs are bipartite, so we are guaranteed to have stable outcomes.) Consider the graphs in Figure 9.1, and let $v (e) = 100$ for every edge $e$ ; think of the value as 100 cents. (Several interesting behavioral experiments have been performed to understand exchange networks in a laboratory setting. In these experiments, subjects are given some small example of a social network—such as the examples in Figure 9.1—and are each assigned to a node in the network, and then need to negotiate a split of a dollar with their neighbors, under the exclusive partnership rule.)

First, look at the leftmost example, consisting of two nodes with a single edge between them. Typically, we would expect the most “fair” outcome to be a 50/50 split of the dollar, but in fact any division is stable, as neither player is able to make a more advantageous deal with another player. (Usually, in behavioral experiments, we do see something close to a 50/50 split; we will shortly return to this point.)
Next, the second example, with three nodes in a line, has only two stable outcomes. The middle player $X$ can choose to partner with $L$ or $R$ , but in any stable outcome he gets all of the 100 units. Otherwise, if $X$ where to partner with, say, $L$ and receives less than 100, then the $(X, R)$ edge has a positive surplus! So we see that $X$ here is “infinitely” powerful—due to its network position, it can extract out all the value!

In the final, rightmost, example, first note that no stable outcome can contain a matching between the middle nodes

(L_{2}, R_{2})

; if it did, one of the nodes (without loss of generality,

L_{2}

) would receive an allocation of at most 50, and there would thus be a surplus of at least 50 between this node and its currently unmatched neighbor (i.e.,

L_{1}

). From this, we conclude that any stable outcome must match

L_{1}

L_{2}

, and

R_{1}

R_{2}

. However, we cannot say much more than this: any allocations of the 100 units over these two edges with the property that

L_{2}

and

R_{2}

receive at least 100 combined (such as the ones illustrated in the figure where, in the first example, all players get 50, and, in the second example,

L_{2}

and

R_{2}

both take 100) will be stable.

Cut-off thresholds: Rejecting unfair deals An important realization from these examples is that nodes on the “ends” of the lines—that is, nodes that are connected to only one other node—have basically no bargaining power; as they have no alternative options, they are forced to take whatever their single prospective partner offers them! However, in real life, even such isolated nodes have some small amount of power. To better understand the issue, consider the following simple game referred to as the ultimatum game:

We have two players, $A$ and $B$ .
$A$ begins by proposing any split of one dollar between himself and $B$ , as long as $B$ is getting at least 1 cent.
$B$ can either accept the split and take the money he is assigned by $A$ , or reject the split, in which case both $A$ and $B$ get nothing.

One might think that splitting the dollar 50/50 would be an equilibrium of this game. But in fact, it is not, since $A$ can always deviate by increasing his cut of the split. In fact, the only PNE of this game is for $A$ to propose that he takes the whole pot (99 cents) and for $B$ to accept (since accepting is strictly dominant for $B$ , and then $A$ best responds by taking the whole pot). This is clearly unrealistic—nobody would accept such an unfair deal in real life! Typically, there is some “cutoff threshold” under which an actual person would find the split to be offensive and refuse it, even if it means that they lose a small amount of money. (In fact, in behavioral experiments, this cut-off threshold has been found to be cultural and to depend on several other factors—for instance, a recent study shows that people typically have a higher cut-off threshold when drunk [MKA14].)

To capture this phenomena in the network exchange setting, we can, given some “actual” exchange network, consider (and analyze) an enlarged “mental-experiment” exchange network where each node gets assigned a new “moon” node $x_{m}$ connected only to $x$ , where the edge $(x, x_{m})$ has a value equal to $x$ ’s cut-off threshold; see Figure 9.2. In this moon-enlarged network, no node $x$ would ever accept a partnership where they earn less than $v (x, x_{m})$ , since then they would just partner with “their moon” $x_{m}$ .

**Figure 9.2:** *Left*: A simple two-node network: $A$ can propose an arbitrarily unfair split (e.g., $100$ to $A$ and $0$ to $B$ ) of the edge weight $100$ . *Middle*: We introduce a “moon” node for $B$ with edge weight 30 to model their refusal to accept any deal where they receive less than 30. In this case, $B$ will prefer to get matched with their “moon” instead of accepting $A$ ’s split from the figure on the left. *Right*: If $A$ proposes a favorable split (in this case, 31), then $B$ will accept it.

9.5 Balanced Outcomes

As seen in even the simple two-node example, where essentially any outcome was stable, stability does not always provide enough predictive power. As such, it would be desirable to have a stronger notion of stability that provides more fine-grained predictions about what outcomes one ought to expect.

Nash bargaining Let us first consider the simple example of a two-node graph. Here, we would expect to see an even split between the players.² This is arguably the “fair” outcome in this simply situation.

But how can we generalize this notion to more complicated graphs? To motivate the definition, consider again a simple two-node network with players $A$ and $B$ and where the value of edge between them is 1, but, now, let us also assume that $A$ has some “outside option” such that he can choose to not match with $B$ and still earn some utility $x$ ; similarly, let $B$ have an outside option, which guarantees him utility $y$ . Let $s = 1 - x - y$ denote the surplus that the two players jointly earn from bargaining with one another instead of taking their outside options. Clearly, $A$ will never accept any offer that gives him less than $x$ , and $B$ will never accept any offer where he earns less than $y$ . So, effectively, they are now negotiating over how their surplus $s$ should be split; effectively, this brings us back to the simple two-node example, where we would expect the surplus to be split evenly.

So $A$ should receive $x + s / 2$ (possibly rounded), and $B$ should receive $y + s / 2$ (possibly rounded); this amounts to a proper split of $v (x, y)$ that is similarly attractive (except for the possible rounding) to both players given their outside options. John Nash, in his paper on bargaining [Nas50a], indeed suggests that this is the “fair” way to set prices in such a bargaining situation.

Defining balanced outcomes We now rely on the Nash bargaining solution to obtain a strong notion of stability for general exchange networks; we say that an outcome is balanced if, for each edge in the matching, the division corresponds to the Nash bargaining solution wherein each node’s “outside options” are defined by the divisions in the rest of the network—namely, the outside option of a node $x$ is defined to be ${max}_{y \neq M (x)} {v (x, y) - d (y)}$ , that is, the maximum value it can earn by making an acceptable offer to some player besides the one it is currently matched with. Note that any balanced outcome clearly also is stable: each node clearly gets at least as much as its outside option, which is what the notion of stability requires.

Revisiting the examples We can now revisit the simple line networks considered in Figure 9.1; for each network, we now have a unique balanced outcome. In the leftmost graph, by definition, the balanced outcome is a 50/50 split. In the second graph, $X$ still gets the full 100 units (as this was the only stable outcome, and as such can also be the only balanced outcome). The most interesting case is the rightmost graph. As argued before, there is not stable matching where the middle nodes $L_{2}, R_{2}$ get matched, and thus they cannot get matched in a balanced outcome either. Note, however, that the middle nodes still have the option of matching with each other and thus have an outside option, whereas the exterior nodes do not (i.e., their outside option is 0). Let $l_{1}, l_{2}, r_{2}, r_{1}$ denote the respective divisions in some balanced outcome. Since $L_{2}$ ’s outside option is $100 - r_{2}$ , and $L_{1}$ outside option is 0, by balance we have that

l_{2} = 100 - r_{2} + (100 - (100 - r_{2})) / 2 = 100 - r_{2} / 2 .

By the same argument, we have that

r_{2} = 100 - l_{2} / 2 .

Solving this linear equation yields the solution $l_{2} = r_{2} = 200 / 3$ ; we conclude that $l_{1} = r_{1} = 100 / 3$ . So, as expected, the interior nodes can leverage the fact that they have better “outside options” to get a better deal (i.e., $\frac{2}{3}$ of the 100 units, whereas the the exterior nodes are only getting $\frac{1}{3}$ ). See Figure 9.3 for a summary.

**Figure 9.3:** Returning to the examples in Figure 9.1, we can analyze the balanced states of each of these by considering each node’s outside options. Outside options are indicated in red, surpluses in blue, and the balanced matchings and splits in purple.

Balanced outcomes indeed provide good predictions of how human players will actually split money in behavioral experiments, not only in the case of a two-node network, but also in more general networks (such as the line networks considered). Additionally, a result by Kleinberg and Tardos [KT08] shows that every exchange network that has a stable outcome also has such an outcome that is balanced; this result, however, is outside the scope of this course.

Notes

Exchange networks for bipartite graphs were first considered by Shapley and Shubik [SS71]; the notion of stability is a special case of the notion of the core introduced by Gillies [Gil59] and studied for exchange networks in [SS71]. As far as we know, exchange networks in general graphs were first considered in [KT08]. The notion of a balanced outcome first appeared in [Roc84, CY92] but the term “balanced” was first coined in [KT08]; as mentioned, the Nash bargaining outcome was first studied in Nash’s paper [Nas50a].

Theorem 9.1 was first proven in [SS71] and a generalized version of it appears in [KT08]; both these proofs rely on heavier machinery (solving linear/dynamic programs). Our proof (relying on the connection between exchange networks and matching markets) is new as far as we know.

Finally, see [EK10, Wil99] for further discussion of behavioral experiments studying exchange networks.

¹If amounts are infinitely divisible, $x$ can always offer $y$ a deal that strictly increases also $y$ ’s allocated amount (by some small $𝜖$ ), while still ensuring that $x$ is strictly better off—this is why we expect $y$ to also want to break its current partnership.

²This may not always be the case; for instance, in situations where one of the players inherently has more “social power” (e.g., the left node is the boss of the right node), we would expect to see an uneven split. Again, this phenomena can be captured by relying on the moon-augmented network mentioned above, where the player with more inherent social power gets a “bigger moon.”