FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 |

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

-- [ Page 1 ] --

Truth-Telling and Nash Equilibria in

Minimum Cost Spanning Tree Models

Jens Leth Hougaard∗ Mich Tvede†


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 find 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 efficient 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 efficient 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 different 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 efficiency.

It is well-known that in general we cannot find incentive compatible and efficient cost allocation mechanisms (Green & Laffont 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 specific 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 first 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 briefly 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 different since it is a simple one-shot game, which is not based on any algorithm for finding the MCST. Moreover, agents’ announcements do not directly influence 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 final 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-benefit) 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 finite. 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 different 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 defined 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: first, 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 finds the associated set of MCSTs. Second, the planner randomly selects an efficient 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 fixed rules of the game agents can choose their announcements strategically. Indeed, by lying an agent can influence the set of efficient 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 satisfies 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 defined 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 ε sufficiently small. Suppose that all agents except z announce the truth.

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


–  –  –

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 finite set of cost matrices known by all agents. Every agent a ∈ N has a probability measure on the finite 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 finite 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

–  –  –

Pages:   || 2 |

Similar works:

«An Evaluation of Postmodernist Aesthetics in Kurt Vonnegut's Slaughterhouse Five Dr. K. CHELLAMUTHU Associate Professor of English, C.P.A Collge, Bodinayakanur. In his address at the library of congress in 1963, Saul Bellow, the celebrated American writer aptly commented on postmodernist American fiction: 'American novels are filled with complaints over the misfortune of the sovereign self '. It is true that the idea of the 'self' received a jolt with the two World Wars and the Russian...»

«Ciência Viva – Geologia no Verão 2010 Caminhando com a Geologia na Serra de Sintra Universidade de Lisboa Ciência Viva – Geologia no Verão Caminhando com a Geologia na Serra de Sintra Caminhando com a Geologia na Serra de Sintra 1 – Enquadramento no sistema Terra Geologia [do grego (ge-, a terra) e (logos, palavra, razão)] é a ciência que estuda o planeta Terra: a sua origem, a sua composição e estrutura, o seu funcionamento e sua história evolutiva. O SOL e todos os planetas do...»

«SUPREME COURT OF CANADA CITATION: Carter v. Canada (Attorney General), 2015 SCC 5 DATE: 20150206 DOCKET: 35591 BETWEEN: Lee Carter, Hollis Johnson, William Shoichet, British Columbia Civil Liberties Association and Gloria Taylor Appellants and Attorney General of Canada Respondent AND BETWEEN: Lee Carter, Hollis Johnson, William Shoichet, British Columbia Civil Liberties Association and Gloria Taylor Appellants and Attorney General of Canada and Attorney General of British Columbia Respondents...»

«Dying Hours 20/03/2013 15:05 Page 1 PROLOGUE How much blood? When he’d finally found the right website, once he’d waded through all the mealy-mouthed crap about having something to live for and trying to seek some kind of professional help, once he’d found a site that really told him what he needed to know, that was the one question they hadn’t answered. All the other stuff was there: how and where to cut, the bathwater helping when it came to raising the body temperature and engorging...»

«Agence Littéraire Lora Fountain Contact: agence@fountlit.com FOR RIGHTS INFORMATION PLEASE CONTACT | Eleanor Shorne Holden, Rights Executive, Phone | 613 8537 4619 Email: | EShorneHolden@penguinrandomhouse.com.au FOR RIGHTS INFORMATION PLEASE CONTACT | Eleanor Shorne Holden, Rights Executive, Phone | 613 8537 4619 Email: | EShorneHolden@penguinrandomhouse.com.au PENGUIN YOUNG READERS YOUNG ADULT ISOBELLE CARMODY THE RED QUEEN: OBERNEWTYN (BOOK 7) The time has come at last for Elspeth Gordie to...»

«Nietzsche’s Problem of the Past John Richardson Nietzsche has a problem with the past. He thinks we all have a problem with it, indeed several interlocking problems, whose chief root he tries to identify. His repeated attention to this topic, coming at key points in his texts, amounts almost to a fixation. My aims are to point out this repeating theme, which I think has been under-recognized, but more importantly to suggest the underlying reasons Nietzsche has for making the past a problem....»

«PRE-PERFORMANCE ACTIVITY ONE: FULL OF VEXATION CURRICULUM LINKS English: ACELT1620, ACELT1622, ACELT1625, ACELY1725, ACLEY1721, ACELT1627, ACELT1632, ACELY1732, ACELY1810, ACELA1552, ACELA1553, ACELA1770, ACELT1771, ACELT1635, ACELT1636, ACELT1773, ACELY1739, ACELY1742, ACELY1743, ACELY1744, ACELY1745, ACELY1746, ACELA1565, ACELT1640, ACELT1812, ACELT1643, ACELT1644, ACELY1749, ACELY1752 Drama: ACADRM040, ACADRR045, ACADRR052. DRAMA AND ANALYSIS ACT 1, SCENE 1 A Midsummer Night’s Dream opens...»

«HCJ 7957/04 Mara’abe v. The Prime Minister of Israel 1 H.C.J. 7957/04 Petitioners: 1. Zaharan Yunis Muhammad Mara'abe 2. Morad Ahmed Muhammad Ahmed 3. Muhammad Jamil Mas'ud Shuahani 4. Adnan Abd el Rahman Daud Udah 5. Abd el Rahim Ismail Daud Udah 6. Bassem Salah Abd el Rahman Udah 7. The Association for Civil Rights in Israel 8. v. Respondents: 1. The Prime Minister of Israel 2. The Minister of Defense 3. The Commander of IDF Forces in the Judea and Samaria Area 4. The Separation Fence...»

«United States Government Accountability Office Report to Congressional Requesters DOD FINANCIAL September 2015 MANAGEMENT Additional Efforts Needed to Improve Audit Readiness of Navy Military Pay and Other Related Activities GAO-15-658 September 2015 DOD FINANCIAL MANAGEMENT Additional Efforts Needed to Improve Audit Readiness of Navy Military Pay and Other Related Activities Highlights of GAO-15-658, a report to congressional requesters Why GAO Did This Study What GAO Found Based on...»

«No. 400 August 26, 2015 365 IN THE COURT OF APPEALS OF THE STATE OF OREGON STATE OF OREGON, Plaintiff-Respondent, v. SCOTT MICHAEL STRYE, Defendant-Appellant. Lane County Circuit Court 201210945; A154702 Mustafa T. Kasubhai, Judge. Argued and submitted January 29, 2015. George W. Kelly argued the cause and filed the brief for appellant. David B. Thompson, Assistant Attorney General, argued the cause for respondent. With him on the brief were Ellen F. Rosenblum, Attorney General, and Anna M....»

«International Journal of Mathematical Engineering and Science ISSN : 2277-6982 Volume 1 Issue 8 (August 2012) http://www.ijmes.com/ https://sites.google.com/site/ijmesjournal/ Somewhat almost sg-continuous functions and Somewhat almost sg-open functions S. Balasubramanian1 and C. Sandhya2 1 Department of Mathematics, Govt. Arts College(A), Karur – 639 005, Tamilnadu 2 Department of Mathematics, C.S.R. Sarma College, Ongole–523001, Andhrapradesh E.mail:mani55682@rediffmail.com1,...»

«Before the FEDERAL COMMUNICATIONS COMMISSION Washington, D.C. 20554 ) In the Matter of: ) ) Petition of United Stationers CG Docket No. 02-278 ) Inc., United Stationers Supply CG Docket No. 05-338 ) Co. and Lagasse LLC for ) Retroactive Waiver of 47 C.F.R. §64.1200(a)(4)(iv) PETITION FOR RETROACTIVE WAIVER Pursuant to Section 1.3 of the Federal Communications Commission’s rules,1 and Paragraph 30 of the Commission’s Order issued on October 30, 2014 (the “Solicited Fax Order”),2...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.