Cutting a link costs both of its ends the same

Three people, and any two of them can do a job worth 1 that no one of them can do alone. All three together can still only do the job once. Averaging what each adds over every order of arrival gives each of them a third, and so would any rule that treats interchangeable people alike.

Now suppose they can only work with somebody they know. A knows C and B knows C, but A and B have never met. A pair can do the job only if it is linked, so A and B together are worth nothing. The value of each group is no longer a fact about its size alone; it depends on the network. And the average over orders, run on the game the network allows, gives C two thirds and A and B a sixth each.

Roger Myerson proposed this in 1977: players cooperate only along the links of a network, a coalition earns only what its connected pieces can earn, and each player is paid the average over orders of that restricted game. He proved it was the unique rule with two properties, one of which is the reason to take it seriously — breaking any link costs its two ends exactly the same. This essay draws the rule, checks that property on every link of two networks, and follows the argument that makes it the only rule that has it.

The game the network allows #

A game on a set of players assigns a value to every coalition. A network is a set of links between pairs of players. The restricted game values a coalition by splitting it into the pieces the network connects — two members are in the same piece if a chain of links among members joins them — and adding what each piece would earn on its own. A coalition whose members are all mutually unreachable earns nothing beyond what they earn alone; a coalition the network holds together earns its full value.

On the triangle every pair is linked, the restricted game is the original one, and the shares are a third each. Remove the link between A and B and the pair A, B becomes worth nothing, while every other coalition is unchanged. Now in the six orders of arrival C is decisive whenever C arrives second — the first arrival alone earns nothing, and C’s arrival joins a pair — and also whenever C arrives third after A and B, who were unable to earn anything together. That is four orders of six, so C’s share is two thirds. A and B are each decisive only when they arrive second behind C, one order each, a sixth apiece.

The shares add up to 1, as the whole network earns 1. Nothing about the players changed except who can reach whom, and the whole of the redistribution came from one missing link.

The cost of a link, to each end #

Cut the link A–B on the line and A is isolated, due nothing; B and C are a linked pair and share the 1 equally. A loses a sixth and B loses a sixth. C gains a third, which is where their losses went: B, who was the player everyone needed, is now one of two equal partners.

The equality of the two losses is not a coincidence of the numbers. It is Myerson’s fairness condition: under his rule, removing any link changes the shares of its two ends by the same amount. The rule does not say links are worth the same to everybody; it says that whatever a link is worth, both of the people it joins have the same stake in it. Neither end can threaten to cut it at the other’s expense, and neither is subsidising the other’s connection.

C’s gain shows what the condition does not say. Players who are not ends of the cut link can gain or lose anything, and here the third player is the one who profits from a link breaking. Only the two ends are bound to each other.

Why the ends always lose the same #

The reason is one of the four conditions the average over orders already satisfies. Compare the restricted game with the link and without it. The two games agree on every coalition that does not contain both ends of the link, since for such a coalition the link is not among its members and cannot join anything. They differ only on coalitions containing both ends.

So take the difference of the two games — itself a game, the value each coalition gains from the link. In that difference game the two ends are interchangeable: any coalition containing one of them and not the other is worth nothing in it, and every coalition containing both is unaffected by which one is which. The symmetry condition gives interchangeable players equal shares, and additivity says the shares in the difference game are the differences of the shares. The two ends’ changes are equal because they are symmetric in the only game where their link matters. It takes four lines and uses none of the arithmetic of the figures.

The other property is simpler. Players in different pieces of the network cannot affect one another’s coalitions at all, so the average over orders of the restricted game divides each piece’s earnings among that piece’s members. Myerson called that component efficiency: every connected piece of the network shares out exactly what it would earn alone.

Why no other rule has both #

The converse is the part worth the essay: any rule that is fair in Myerson’s sense and shares out each piece’s earnings must give these numbers.

The argument is an induction on the number of links. With no links at all every player is a piece of one, and sharing out each piece’s earnings pays each player exactly what they earn alone — there is nothing to choose. Now suppose a rule is pinned down on every network with fewer links than some network $G$, and look at $G$. For each link $ij$ in $G$, fairness says

$$\text{share}_i(G) - \text{share}_j(G) = \text{share}_i(G - ij) - \text{share}_j(G - ij),$$

and the right side is already known, because $G - ij$ has one link fewer. So for every pair of linked players, the difference of their shares is determined. Within a connected piece every two players are joined by a chain of links — a spanning tree of the piece reaches them all — so every difference within the piece is determined, and one more equation, that the piece’s shares add up to what it earns, fixes the level. Every share on $G$ is forced.

Two conditions, then, and exactly one rule meets them. That parallels the first theorem about this rule, where four conditions forced the average over orders on a game with no network; here two conditions, both stated in terms of links, force the same average on the restricted game.

On a tree, a share is half of each link #

One game makes the rule transparent. Let a connected piece of $k$ players earn $k - 1$ — one unit for each link it would take to hold $k$ players together, the fewest links a connected piece can have. On a network with no loops, a tree, every connected piece of a coalition is itself a tree, and a tree on $k$ players has exactly $k - 1$ links. So the restricted game values every coalition at the number of links among its own members.

That game is a sum of very simple ones, one per link, each worth 1 to any coalition that contains both of the link’s ends and nothing otherwise. In each of those the two ends are interchangeable and everybody else adds nothing, so the average over orders gives each end a half. Adding up over links, each player’s share is half the number of links they hold. On a tree, and for this game, counting links is exactly right.

The game is chosen to make that true, and the moment a loop appears it stops being true: a triangle’s three links hold three players together, but the game pays only 2, and the three links share it. On networks with loops, and for games that pay for something other than bare connection, the shares drift away from the link count, and how far they drift is a measure of where the network’s value really sits. The go-between below is the clearest case, and a tree of cuts is another way of asking the same question — which links the network cannot spare.

A go-between with two links #

On three players the network’s effect is easy to see. On more it is less predictable, and the obvious guess — that a player’s share follows how many links they hold — fails at once.

Here the game is different: every pair of players who can reach each other earns 1, so a connected piece of $k$ players earns $k(k-1)/2$, and the whole network, being connected, earns 21. The value counts connections rather than jobs, and a player is valuable in proportion to how many pairs their presence connects.

D has two links and the largest share. C and E have three links each and less; the four players at the outer corners have two links each and much less. D’s links are the only route between the two triangles, and in every order in which D arrives after C and E, D’s arrival joins everything C has gathered to everything E has gathered, all at once. C and E are each also on that route but each has a triangle behind them that already holds together without them — A and B have each other. The share follows what the network cannot do without, not how many links a player holds.

This is why Myerson’s value has been proposed as a measure of importance in a network: Daniel Gómez and co-authors did so in 2003, measuring a player’s centrality by how far the network moves their share from what the same game would pay them with every link present. It rewards go-betweens in the way that counting links does not, and unlike most measures of importance it comes with a statement of what it is fair to — the two conditions above.

Two links, two very different costs #

Cut the link between C and D and the network falls into two pieces: the triangle A, B, C, earning 3, and the rest, four players earning 6. Twelve of the 21 connections are lost. C and D lose exactly the same, about 3.30 each, as the fairness condition requires, and every other player loses something, because every other player was part of pairs that could only be connected through that link. The losses add up to the twelve connections, and the two ends between them bear more than half.

Cut instead the link between A and B, at the far corner of a triangle, and nothing is disconnected: A and B can still reach each other through C, and the network still earns all 21. Yet the shares move. A and B each lose a sixth, and C gains a third — exactly the three-player line from the start of the essay, reappearing inside a network of seven. A link that carries no connection the network lacks without it is still worth something to its ends, because it lets them bypass C, and the value of bypassing C is what C collects when the link goes.

The two cuts show the rule pricing links, not merely players. The bridge C–D costs its ends 3.30 each; the redundant A–B costs its ends a sixth each. Both prices are split equally between the two ends, and both are paid in part to or by players who hold neither end.

Why the two ends agree about every link #

The fairness condition has a consequence for how networks form, and it is why Matthew Jackson and Asher Wolinsky gave Myerson’s rule a central place in their 1996 model of how networks form. Suppose the players decide for themselves which links to make, and a link is made when both of its ends want it. Under a rule that let one end gain from a link while the other lost, links would be refused that the network as a whole would value, and the structure that formed would depend on who could veto whom.

Under Myerson’s rule that cannot happen. Adding a link changes its two ends’ shares by the same amount, so they always agree: either both gain, and the link is made, or both lose, and neither proposes it. What remains to be decided is only whether the link is good for the two people it joins, and never how to divide the gain between them.

That is not the same as the network that forms being the best one. A link can be good for its two ends and bad for everybody else — the cut of A–B above shows the reverse, a link whose loss hurts its ends and pays a third player — and Jackson and Wolinsky showed that the networks the players would form and the networks that earn the most can differ, under this rule and under every rule in a large family. The agreement between the two ends is local, and the tension between local and global choices of links is a subject of its own, as far from the average over orders as random networks that join up all at once are from networks anybody chose.

What the pictures cannot show #

Every network is small enough to list its orders. Seven players have 5,040 orders and 128 coalitions, and each value above is computed exactly both ways — by orders and by the subset formula — and checked to agree. A network of a few hundred players cannot be handled this way, and sampling orders is the general method there, with the same reciprocal-square-root rate as before.

The two games are chosen to make the network’s effect visible. Under other games on the same networks the shares would differ, and the go-between’s advantage in particular depends on a game that rewards connecting pairs; a game that paid only for the whole network being connected would treat every player whose removal disconnects it alike.

And the fairness condition is a choice, not a law. It is a natural requirement, and it is the one Myerson’s rule uniquely meets. A different notion of fairness — one that let a player’s stake in a link depend on who else they are linked to, say — would pick out a different rule, and nothing drawn here argues that equal stakes are right, only what follows from asking for them.

What the network added #

The first question asked of this rule was about a game in which any group could form: what is each player due? A share of the votes showed that the answer ignores what players appear to hold and tracks what they are needed for; explaining a prediction showed that the answer depends on how the game is built before the rule is applied. The network is one more way of building the game, and the most concrete: remove the coalitions that cannot meet, and run the same average on what is left.

What the network adds is a question the plain game could not ask — what is a link worth, and to whom? — and a clean answer to it. Every link is worth the same to its two ends, whatever it is worth in total, and the rule that says so is the only one that also shares out each connected piece’s earnings among its own members. That is also a core-like guarantee of a weaker kind: no piece of the network is ever asked to pay for another.

When cooperation runs along links, value the coalitions by their connected pieces and average over orders — the ends of every link then have the same stake in it, and the players the network cannot do without are paid for it, whatever their number of links.