Each user pays for its own last link

The corners are the orders of arrival found a condition under which every reasonable way of dividing a group’s gain agrees: when a newcomer always adds at least as much to a bigger group, the core is the outline of the orders of arrival, and the average over those orders sits inside it. That condition is economies of scale in its cleanest form, and most real sharing problems have economies of scale somewhere and not everywhere.

Connecting users to a source is the standard example of somewhere and not everywhere. Some villages must be joined to a well, some buildings to a server, some houses to a main. Every pair of places can be linked at a known cost, and the users may link through one another, so the cheapest network joining everybody to the source is a tree: it has no loops, because a loop always contains a link whose removal leaves everyone connected and saves money. The question is how the tree’s cost should be divided.

In the figure, $A$ and $C$ sit two units from the source and $B$ sits nine units away — but $B$ is only one unit from each of the others. Alone, $B$ would pay $9$ for its connection. Together, the three are served by a tree costing $4$: source to $A$, $A$ to $B$, $B$ to $C$. The bill is $4$, and the question is who pays what.

The groups that could walk away #

A division of the bill is acceptable to a group of users only if the group is not asked to pay more than it would cost them to build their own connection to the source, using their own sites as junctions and nobody else’s. That is the core again, with the inequality turned round, since here a coalition objects to paying too much rather than to receiving too little. Each group’s own cost is the cheapest tree joining its members to the source, and there are seven groups.

$A$ alone would pay $2$, $C$ alone $2$, $B$ alone $9$. The pair $A$ and $B$ would pay $3$ — two to the source, one across — and so would $B$ and $C$; $A$ and $C$ together would pay $4$. So an acceptable division of the $4$ must charge $A$ at most $2$, $C$ at most $2$, $A$ and $B$ together at most $3$, and $B$ and $C$ together at most $3$. The last two force $A$ and $C$ to pay at least $1$ each, and what is left for $B$ is at most $2$.

The rule in the figure charges $(2, 1, 1)$: $A$ pays for the link from the source, $B$ for the link from $A$, $C$ for the link from $B$. Every group’s constraint holds, and three of the seven hold with equality. It is a division no group of users can refuse.

The rule, and why it never overcharges #

The rule is Bird’s rule, published by Claus Bird in 1976, and it is stated in one sentence: build the cheapest tree, hang it from the source, and charge each user the cost of the link that joins it to its parent — the next place on its path to the source.

That it is acceptable to every coalition has a proof that is as short as the rule. Suppose some group $S$ is charged more by Bird’s rule than its own cheapest connection costs. Take $S$’s own cheapest tree, which joins $S$ to the source, and add to it, for every user outside $S$, that user’s link to its parent in the big tree. Every outside user can now follow parent links until it reaches either the source or a member of $S$, both of which are connected; so the result joins everybody. It has one link per user, so it is a tree. Its cost is $S$’s own cost plus what Bird’s rule charges the outsiders — which, if $S$ were overcharged, would be less than what Bird’s rule charges everybody, which is the cost of the cheapest tree. A tree cheaper than the cheapest tree is impossible, so no group is overcharged.

The argument never enumerates groups and never computes a stand-alone cost. It swaps one set of links for another and compares totals, which is the same move the greedy algorithms for cheapest trees are proved correct by: an exchange of one link for another can never lower the cost of a tree that is already cheapest. The fairness of the division is a corollary of the optimality of the tree.

Why the cheapest tree is easy to find #

The rule presupposes the cheapest tree, and it is worth seeing why that tree is easy to find, because the reason is the same one that makes the rule fair.

A network on $n$ places has an enormous number of spanning trees — for four places linked every way, sixteen, and for $n$ places $n^{n-2}$, which a determinant that counts trees derives from the network’s matrix. Searching them is out of the question. What makes the search unnecessary are two exchange facts. The cut rule: divide the places into two parts any way at all, and the cheapest link crossing between the parts belongs to some cheapest tree. The cycle rule: in any loop, the most expensive link belongs to no cheapest tree, unless it ties. Both are proved by the same swap: a tree that broke either rule could exchange one link for another and get cheaper.

Those are statements about cuts and cycles of a graph, the two families of edge sets that the cycles and the cuts found to be complementary, and each one yields an algorithm. Prim’s grows a single tree from the source, repeatedly taking the cheapest link out of the part already built — the cut rule applied to the cut around the growing tree. Kruskal’s sorts all links and takes each one unless it closes a loop — the cycle rule applied in reverse. Both are greedy, both are fast, and neither ever reconsiders a choice.

Prim’s version is the one that matches Bird’s rule. It grows the tree outward from the source, and each link it adds joins a new user to the part already connected; that link is exactly the one Bird charges the new user. The order in which Prim’s algorithm reaches the users is an order of arrival, and Bird’s division is the split that order gives when each user pays its own joining link rather than its effect on anyone else’s cost.

When the places are points in the plane and the costs are straight-line distances, there is a further shortcut: the cheapest tree uses only links between points that are neighbours in the Delaunay triangulation, the dual of the plane divided by whoever is nearest. The nine scattered users below are linked every way, and only a handful of the forty-five possible links among the ten places could ever have been chosen.

The average over orders, and where it goes wrong #

The natural competitor is the rule the order everybody arrives in established for gains: let users arrive one at a time, charge each the extra cost its arrival causes, and average over every order.

In this network the average charges $A$ one third, $B$ ten thirds, $C$ one third. It is easy to see why $B$’s share is large: in the two orders where $B$ arrives first, $B$ must be connected on its own and pays $9$. The average spreads that cost thinly over six orders, and $B$ ends up owing $10/3$.

But then the pair $A$ and $B$ is charged $11/3$ in total, and it could connect itself for $3$ — two units to the source from $A$, one across to $B$. The same holds for $B$ and $C$. The average charges a pair more than its own connection costs, so under the average rule the pair would rather build its own network, and the grand tree would not be built.

The picture of all divisions shows how far the average is from acceptable. The core is a square: $A$ and $C$ each pay between $1$ and $2$, and $B$ pays whatever is left. Bird’s division sits at one corner. The average sits in the far corner of the triangle, near B pays it all, outside the square entirely. What went wrong is the property the corners are the orders of arrival required: a user’s extra cost should shrink as the group it joins grows, and here it does not uniformly. $A$ adds $2$ to an empty network. Joining $B$ alone, it saves $6$ — it gives $B$ a route of three units in place of nine — but joining $B$ and $C$ together it adds $1$, because $C$ has already given $B$ a short route and $A$ has nothing left to offer. The extra cost of a newcomer rises as the group grows from $B$ to $B$ and $C$, which is the reverse of economies of scale. Connection costs have economies of scale in some directions and not others, and the average needs them in all.

Two cheapest trees, two fair divisions #

The network in the first figure has a tie. The tree through $A$ — source to $A$, $A$ to $B$, $B$ to $C$ — costs $4$, and so does the mirror image through $C$. Bird’s rule depends on which tree is built, and the two trees give $(2, 1, 1)$ and $(1, 1, 2)$.

Both are in the core, as the proof requires, and they are opposite corners of the square. That is typical: when cheapest trees tie, each one gives a Bird division, every one of those divisions is acceptable, and any average of them is acceptable too, because the core is convex. The rule is not a single answer but a family of them indexed by the trees, and choosing among them is choosing which tree to build.

It also shows that Bird’s rule is not symmetric, which is the objection most often raised against it. $A$ and $C$ are placed identically — each two units from the source and one from $B$ — and one of them pays twice what the other pays, depending on which way the tree runs. A symmetric rule can be recovered by averaging the two trees’ divisions, which here gives $(3/2, 1, 3/2)$, still in the core.

A core with no width #

Change the costs and the core can collapse to a line.

Here $A$ and $B$ are four units from the source and $C$ is eight — but $C$ is one unit from $A$. The tree costs $9$: both near users link directly to the source, and $C$ hangs off $A$. Bird’s rule charges $(4, 4, 1)$. $C$, whose own connection would cost $8$, pays $1$, and nobody can complain, since $A$ pays for the link $A$ would have paid for anyway.

Two constraints pin $B$’s share exactly: $B$ alone would pay $4$, so $B$ pays at most $4$; $A$ and $C$ together would pay $5$, so they pay at most $5$ and $B$ at least $4$. The core is a segment along which $A$ and $C$ divide their $5$, and Bird’s division is one end of it. The average over orders again lands outside, this time charging $A$ and $C$ together $31/6$ where their own connection costs $5$. The drawing shows only divisions in which nobody is paid; the segment continues past the edge of the triangle into divisions that pay $A$ to take part, which a core for costs allows and a picture of shares does not.

Nine users and every group #

A three-user network proves nothing about Bird’s rule that the swap argument does not already prove, and the argument covers every network. What a larger example shows is how tightly the rule sits against the constraints.

With nine users there are $511$ groups, and each group’s own cheapest connection is a separate tree computation. The figure performs all of them and compares each with the group’s total Bird charge. None is overcharged, which is the theorem. Eighty-nine are charged exactly their own cost, which says how little room the rule leaves: those groups are indifferent between staying and leaving, and a rule that moved even a unit of cost onto any of them would lose them.

The tight groups are not an accident. Take any group that contains, along with each of its members, that member’s whole path to the source — a piece of the tree growing outward from the source. Bird’s rule charges it exactly the links of that piece, and the piece is a connection the group could build on its own, so the group pays no less than its own cost and, by the theorem, no more. Every such piece of the tree is held exactly to its own cost, and a tree with nine users has a great many of them.

A rule that is symmetric and still fair #

Bird’s rule is fair to every coalition and unfair to symmetry; the average over orders is symmetric and unfair to coalitions. A rule with both properties exists, and it comes from changing the game rather than the rule.

Replace every link’s cost with the smallest achievable bottleneck between its ends — the least possible value of the most expensive link on a path between them. Cheapest trees are unchanged, since a cheapest tree is exactly a tree in which every path’s most expensive link is as cheap as possible. But the game changes: in the remote network, $A$ to $C$ now costs $1$, through $B$, and the source to $B$ costs $2$, through $A$. In the new game every user adds less to a bigger group, so the average over orders is back in the core — here it charges $4/3$ each. That average, applied to the bottleneck costs, is called the folk solution of the connection problem, and it is symmetric, it is in the core of the original game, and it has been characterised by several independent lists of fairness conditions. The convexity that the orders of arrival needed was missing from the original costs and present in their bottlenecks.

What the network pictures cannot show #

The networks are small and their costs are chosen. Three users make a triangle of divisions in which a core can be seen whole; nine users are shown only as a tree with charges beside it, since their core lives in eight dimensions. The two three-user networks were found by searching thousands of random cost tables for ones where the average over orders falls outside the core and the core is still large enough to see.

The rule is checked against every group only where the groups can be counted. For nine users that is $511$ trees, each found by Prim’s algorithm. The theorem for every network is the swap argument, which the figures do not draw; the exhaustive check is evidence that the implementation agrees with the theorem, not a substitute for it.

Only junctions belonging to the group are allowed. A group building its own connection may route through its own members’ sites and no one else’s. If a group could route through any site — a crossroads that belongs to nobody, or another user’s building — its own cost becomes a Steiner tree, whose exact computation is one of the problems Richard Karp listed in 1972 as NP-complete, and the game and its core change with it. None of that is drawn.

Still open: how fast the cheapest tree can be found #

Everything here rests on the cheapest tree, and the tree is easy to find: Otakar Borůvka gave the first algorithm in 1926, Joseph Kruskal and Robert Prim the two usually taught in 1956 and 1957, each growing the tree one cheapest safe link at a time. For a network with $m$ links they take time roughly proportional to $m$ times a logarithm.

Whether that logarithm is necessary is open. David Karger, Philip Klein and Robert Tarjan found in 1995 a randomised algorithm whose expected running time is proportional to $m$ — as fast as reading the links. Bernard Chazelle found in 2000 a deterministic one slower than that by only an extremely slowly growing factor, and Seth Pettie and Vijaya Ramachandran found in 2002 a deterministic algorithm that is provably optimal — without anyone being able to say what its running time is. Whether the cheapest tree can be found deterministically in time proportional to the number of links is not known, and it is one of the few basic questions about graphs whose answer might be a surprise either way.

The division comes from the tree #

The habit worth keeping is the proof’s.

A division of a cost is usually argued for by listing properties it should have and checking them against every coalition, which is a search with $2^n$ cases. Bird’s rule needs none of that, because it is read off the object that solves the underlying problem: the cheapest tree. Each user pays the link that joins it, and any group that thought it was overcharged would, by building its own tree and borrowing the outsiders’ links, have built a tree cheaper than the cheapest one. The fairness of the division is the optimality of the tree, read one user at a time.

That is the same shape as the certificates that closed the question of an empty core in five weighings: an argument about one optimal object replaces a search over every coalition. Where the cost has a structure — a tree, a runway, a set of orders — the fair division is usually hiding in it, and the average over orders, which knows nothing about the structure, is the rule most likely to miss it.