Out in a rural part of the county somewhere, n small towns have decided to get connected t...

Out in a rural part of the county somewhere, n small towns have decided to get connected to a large Internet switching hub via a high-volume fiber-optic cable. The towns are labeled T1, T2,…, Tn, and they are all arranged on a single long highway, so that town Ti is i miles from the switching hub (See Figure 1).

Now this cable is quite expensive; it costs k dollars per mile, resulting in an overall cost of kn dollars for the whole cable. The towns get together and discuss how to divide up the cost of the cable.

First, one of the towns way out at the far end of the highway makes the following proposal.

Proposal A. Divide the cost evenly among all towns, so each pays k dollars.

There's some sense in which Proposal A is fair, since it's as if each town is paying for the mile of cable directly leading up to it.

But one of the towns very close to the switching hub objects, pointing out that the faraway towns are actually benefiting from a large section of the cable, whereas the close-in towns only benefit from a short section of it. So they make the following counterproposal.

Proposal B. Divide the cost so that the contribution of town Ti is proportional to i, its distance from the switching hub.

One of the other towns very close to the switching hub points out that there's another way to do a nonproportional division that is also natural. This is based on conceptually dividing the cable into n equal-length "edges" e1,…,en, where the first edge e1 runs from the switching hub to T1, and the ith edge et (i > 1) runs from Ti–1 to Ti. Now we observe that, while all the towns benefit from e1, only the last town benefits from en. So they suggest

Proposal C. Divide the cost separately for each edge ei. The cost of ei should be shared equally by the towns Ti, Ti + 1,2026 Tn, since these are the towns "downstream" of ei.

So now the towns have many different options; which is the fairest? To resolve this, they turn to the work of Lloyd Shapley, one of the most famous mathematical economists of the 20th century. He proposed what is now called the Shapley value as a general mechanism for sharing costs or benefits among several parties. It can be viewed as determining the "marginal contribution" of each party, assuming the parties arrive in a random order.

Here's how it would work concretely in our setting. Consider an ordering O of the towns, and suppose that the towns "arrive" in this order. The marginal cost of town Ti in order O is determined as follows. If Ti is first in the order O, then Ti pays ki, the cost of running the cable all the way from the switching hub to Ti. Otherwise, look at the set of towns that come before Ti in the order O, and let Tj be the farthest among these towns from the switching hub. When Tt arrives, we assume the cable already reaches out to Tj but no farther. So if j > i (Tj is farther out than Ti), then the marginal cost of Tt is 0, since the cable already runs past Ti on its way out to Tj. On the other hand, if jt is k(i – j): the cost of extending the cable from Tj out to Ti.

(For example, suppose n = 3 and the towns arrive in the order T1, T3, T2. First T1 pays k when it arrives. Then, when T3 arrives, it only has to pay 2k to extend the cable from T1. Finally, when T2 arrives, it doesn't have to pay anything since the cable already runs past it out to T3.)

Now, let Xt be the random variable equal to the marginal cost of town Ti when the order O is selected uniformly at random from all permutations of the towns. Under the rules of the Shapley value, the amount that Ti should contribute to the overall cost of the cable is the expected value of Xi.

The question is: Which of the three proposals above, if any, gives the same division of costs as the Shapley value cost-sharing mechanism? Give a proof for your answer.