# «Abstract In this paper we consider the Minimum Cost Spanning Tree model. We assume that a central planner aims at implementing a minimum cost ...»

Truth-Telling and Nash Equilibria in

Minimum Cost Spanning Tree Models

Jens Leth Hougaard∗ Mich Tvede†

Abstract

In this paper we consider the Minimum Cost Spanning Tree model.

We assume that a central planner aims at implementing a minimum

cost spanning tree not knowing the true link costs. The central planner

sets up a game where agents announce link costs, a tree is chosen and

costs are allocated according to the rules of the game. We character-

ize ways of allocating costs such that true announcements constitute Nash equilibria both in case of full and incomplete information. In particular, we ﬁnd that the Shapley rule based on the irreducible cost matrix is consistent with truthful announcements while a series of other well-known rules (such as the Bird-rule, Serial Equal Split, the Proportional rule etc.) are not.

Keywords: Bayesian Nash equilibrium, Incomplete information, Minimum cost spanning tree, Shapley value, Nash equilibrium, Truth-telling.

Acknowledgements: The authors wish to thank Gustavo Bergantinos, Herv´ Moulin, Kurt Nielsen and Katrine Stagaard for helpful comments.

e ∗ Corresponding author: Institute of Food and Resource Economics, University of Copenhagen, Rolighedsvej 25, DK-1958 Frederiksberg C., Denmark, phone +45 35 33 68 14, email: jlh@foi.dk † Department of Economics, University of Copenhagen, Oester Farimagsgade 5, DK- 1353 Copenhagen K, Denmark, phone +45 35 32 30 92, email: mich.tvede@econ.ku.dk 1 1 Introduction Recently, economists have shown a growing interest in networks and the lit- erature is becoming rich on various issues and models, see e.g. Goyal (2007) and Jackson (2008). In the present paper we consider the relation between cost allocation and eﬃcient network structure within the classical Minimum Cost Spanning Tree (MCST) model. Here, a group of agents is to be con- nected to a source (supplier) in the least costly way and face the problem of sharing the cost of the eﬃcient network, see e.g. Sharkey (1995) — practical examples include district heating, computer network using a common server, cable tv, chain stores using a common warehouse etc.

While the literature typically contains axiomatic analysis and compar- isons of diﬀerent cost sharing methods there has been less emphasis on strategic issues concerning practical implementation. Clearly, agents can have private information about the cost structure. This information they can use strategically to lower their own cost at the expense of a loss in social eﬃciency.

It is well-known that in general we cannot ﬁnd incentive compatible and eﬃcient cost allocation mechanisms (Green & Laﬀont 1977), but under spe- cial circumstances such mechanisms can in fact be constructed, see e.g. Jack- son & Moulin (1992), Schmeidler & Tauman (1994), Young (1998), Moulin & Shenker (2001). For social choice rules Maskin (1999) and Dasgupta, Hammond & Maskin (1979) show that implementability and monotonicity are equivalent. We consider monotonicity of cost allocation rules and present compatible results for the MCST model.

In the speciﬁc context of the MCST model, implementation has been analyzed in a few recent papers; Bergantinos & Lorenzo (2004, 2005) and Bergantinos & Vidal-Puga (2010). All three papers consider existence and properties of Nash equilibria and subgame perfect Nash equilibria of noncooperative sequential bargaining procedures. The ﬁrst two papers study a real life allocation problem where agents sequentially join an existing network along the lines of the Prim algorithm (Prim 1957). The latter paper shows that another Prim-like procedure, where agents announce their willingness to pay for other agents to connect to the source, leads to a unique subgame 2 perfect Nash equilibrium in which costs are allocated corresponding to the use of the Shapley value on the related irreducible cost matrix (dubbed the Folksolution in Bogomolnaia & Moulin 2010 and further analyzed in Bergantinos & Videl-Puga 2007, 2009 and Hougaard et al. 2010).

In the present paper, Section 2 brieﬂy reviews the MCST model and Section 3 introduces a noncooperative game form involving a planner who does not know the link costs and a set of agents who all know the link costs.

First the planner announces the rules of the game being an allocation rule and an estimation rule. Then agents announce the link costs, which in turn are used to estimate a cost matrix and its related set of MCSTs. A particular MCST is selected at random and the realized link costs are shared between the agents according to the announced allocation rule.

Compared to the Prim-like sequential mechanisms mentioned above our approach is diﬀerent since it is a simple one-shot game, which is not based on any algorithm for ﬁnding the MCST. Moreover, agents’ announcements do not directly inﬂuence their cost shares since these are determined by the realized costs along the chosen spanning tree.

In Section 4 our main result is established: announcing the true link costs constitutes a Nash equilibrium if and only if the associated allocation rule is monotonic (in the sense that cost shares are weakly increasing in the irreducible cost matrix). Consequently, monotonic allocation rules such as the Shapley rule (on the irreducible cost matrix) and the Equal Split rule will both result in truth-telling Nash equilibria where the planner can implement the true MCST. However, well-known rules such as the Bird rule and the Proportional rule fail to satisfy monotonicity.

In Section 5 we consider an incomplete information version of the game along the lines of Jackson (1991). We show that truth-telling remains an equilibrium for monotonic allocation rules. Section 6 closes with some ﬁnal remarks.

2 The MCST Model Recall the minimum cost spanning tree model (see e.g. Sharkey 1995). Networks, where a source supplies agents with some homogeneous good, are 3 considered. Let 0 be the source and let N = {1,..., n} be the set of agents.

A network g over N 0 = {0}∪N is a set of unordered pairs ab, where a, b ∈ N 0.

Let N 0 (2) be the set of unordered pairs and let G0 = {g|g ⊂ N 0 (2)} be the set of all networks over N 0.

In a network g two agents a and b are connected if and only if there is a path i1 i2, i2 i3,..., im−1 im such that ih ih+1 ∈ g for 1 ≤ h ≤ m − 1 where i1 = a and im = b. A network g is connected if a and b are connected for all a, b ∈ N 0. A path is a cycle if it starts and ends with the same agent. A network is a tree if it contains no cycles. A spanning tree is a tree where all agents in N 0 are connected. There are (n + 1)n−1 spanning trees.

For every pair of agents ab ∈ N 0 (2) there is a net-cost kab ∈ R attached to the link between a and b. If kab ()0, then there is a net-cost (net-beneﬁt) of establishing the link. For N 0 let the (n + 1) × (n + 1)-matrix K be the net-cost matrix. The model is a slight generalization of the standard MCST model because link costs can be positive as well as negative. An allocation problem is a set of agents and a net-cost matrix, (N, K).

For a spanning tree p, let v(N, K, p) = ab∈p kab be the total net-cost of p. A minimum cost spanning tree (MCST) is a spanning tree p such that v(N, K, p) ≤ v(N, K, q) for every spanning tree q. For every allocation problem (N, K) there exists a MCST because the number of spanning trees is ﬁnite. Let v(N, K) denote the minimal cost so there exists a spanning tree p such that v(N, K, p) = v(N, K) and v(N, K, q) ≥ v(N, K) for every spanning tree q. If all net-costs kab are diﬀerent then there is a unique MCST, but in general there can be several MCSTs. Indeed, if all net-costs kab are equal, then every spanning tree is a MCST. Let T (N, K) be the set of MCSTs.

Irreducible matrices For two matrices K and K the matrix K is smaller than K if and only if kab ≤ kab for all a, b ∈ N 0. The irreducible matrix C(K) for a net-cost matrix K is the smallest matrix C such that v(N, C) = v(N, K) and cab ≤ kab for all a, b ∈ N 0, see e.g. Bird (1976), Aarts & Driessen (1993). For a net-cost matrix K and a spanning tree p the irreducible matrix C(K, p) is deﬁned as follows: For every a, b ∈ N 0, let pab be the unique path in p from a to b,

Allocation Rules Let Γ be the set of allocation problems and their spanning trees so (N, K, p) ∈ Γ if and only if (N, K) is an allocation problem and p is a spanning tree for (N, K). An allocation rule φ : Γ → RN maps an allocation problem (N, K) and a spanning tree p to an n-dimensional vector of net-costs φ(N, K, p) = (φ1 (N, K, p),..., φn (N, K, p)).

Only allocation rules that are budget balanced, reductionist1 and continuous are considered.

• Budget-balance: a∈N φa (N, K, p) = v(N, K) for all p ∈ T (N, K), so cost shares add up to the total cost of the MCST.

• Reductionist: φa (N, K, p) = φa (N, C(K, p), p) for all spanning trees p, so cost shares depend on the irreducible matrix of the chosen spanning tree.

• Continuity: φ(N, K, p) is continuous in K.

Budget-balance and continuity are standard properties of allocation rules.

Budget-balance implies that exactly the net-cost of every spanning tree is allocated. The reason we consider reductionist rules will become clear once the implementation setting is presented.

For a spanning tree p, let δ(a, b, p) be the unique neighbor of a in the path pab from a to b in p, then some examples of (continuous, budget-balanced and

**reductionist) allocation rules are:**

where s is the number of agents in S and v(S, C(K, p)) is the minimal cost of connecting all members of S to the source 0 given C(K, p).2 3 The Game In this section a two-stage game between a central planner and a set of agents is introduced. The planner aims at minimizing the cost of connecting all agents to the source, but the planner does not know the link costs. Every agent aims at minimizing his connection cost and knows all link costs.

The game is as follows: ﬁrst, the planner announces the rules of the game, i.e. an estimation rule and an allocation rule. Then every agent announces (simultaneously and independently) all link costs to the planner who use the estimation rule to estimate the cost matrix based on these announcements and ﬁnds the associated set of MCSTs. Second, the planner randomly selects an eﬃcient spanning tree among this set and uses the allocation rule to distribute the observed (true) costs of the selected spanning tree to the agents.

The announcements are used to select a spanning tree because the announcements are used to estimate link costs. However, the announcements are not used to distribute observed costs.

2 In our context the Shapley value coincides with the so-called Folk-solution considered in Bergantinos & Vidal-Puga (2007, 2009) and Bogomolnaia & Moulin (2010).

For ﬁxed rules of the game agents can choose their announcements strategically. Indeed, by lying an agent can inﬂuence the set of eﬃcient spanning trees given the estimated link costs and thereby manipulate his resulting cost share.

Example: Consider the Proportional Rule φP. Let N = {1, 2, 3} and let

The example indicates that some form of monotonicity of the allocation rules is crucial for truth-telling.

(M) Monotonicity: An allocation rule is monotonic provided that for two spanning trees p and q, if C(K, p) is smaller than C(K, q), then

Neither the Bird rule nor the Proportional rule satisfy monotonicity. However, both the Equal Split rule and the Shapley rule satisﬁes monotonicity. In fact, the set of monotonic rules is quite large and also includes, for instance, the family of obligation rules introduced and analyzed in Tijs et al. (2006).

4 Implementation of MCSTs The relation between truth-telling as a strategy and monotonic allocation rules is characterized below.

Theorem 1 Truth-telling is a Nash equilibrium for every allocation problem if and only if the allocation rule is monotonic.

Proof: Suppose that an allocation rule is monotonic. Then no agent can gain by deviating from truth-telling, because the irreducible matrix is minimal for truth-telling.

Suppose that an allocation rule is not monotonic. Then there exists an allocation problem (N, K) and spanning trees p and q such that C(K, q) ≥ C(K, p) and φz (N, C(K, q), q) φz (N, C(K, p), p) for some z ∈ N. Let a new problem (N, K ) be deﬁned by kab = kab for all ab ∈ p, kab = kab + ε for ab ∈ q \ p for ε 0 and kab = maxa b {ka b } + 1 otherwise. Then p is the unique MCST in (N, K ) and φz (N, K, q) φz (N, K, p) by continuity for ε suﬃciently small. Suppose that all agents except z announce the truth.

Then z can gain by announcing the truth for all links in q and suﬃciently high costs for all other links. Indeed q is the unique MCST for (N, K e ) because τ is upward unbounded.

Q.E.D.

The proofs of Theorems 1 and 2 demonstrate the importance of lies.

In both proofs an agent manipulates the estimated link costs by lying about non-realized link costs showing that attempts by the planner to enforce truthtelling by punishing observed lies are in vain.

Next we demonstrate that Theorem 1 generalizes to situations where agents have incomplete information about costs, while Theorem 2 does not.

5 Incomplete information Let {K1,..., Km } be a ﬁnite set of cost matrices known by all agents. Every agent a ∈ N has a probability measure on the ﬁnite set of cost matrices μa : {K1,..., Km } → [0, 1] with μa (K) 0 for all K ∈ {K1,..., Km }. In addition every agent a ∈ N has a signal from the ﬁnite set of cost matrices to subsets of that set sa : {K1,..., Km } → 2{K1,...,Km } where sa (K) is the

**private information of agent a ∈ N at K. For signals it is assumed that:**

1. if the true matrix is K, then K is part of the private information at K;

2. the matrix K is part of the private information at K if and only if K is part of the private information at K ; and, 3. the intersection of all private