Implementing Efficient Graphs in Connection Networks

Ruben Juarez () and Rajnish Kumar ()

No 201203, Working Papers from University of Hawaii at Manoa, Department of Economics

Abstract: We consider the problem of sharing the cost of a network that meets the connection demands of a set of agents. The agents simultaneously choose paths in the network connecting their demand nodes. A mechanism splits the total cost of the network formed among the participants. We introduce two new properties of implementation. The first property, Pareto Nash Implementation (PNI), requires that the ecient outcome always be implemented in a Nash equilibrium and that the efficient outcome Pareto dominates any other Nash equilibrium. The average cost mechanism (AC) and other asymmetric variations are the only rules that meet PNI. These mechanisms are also characterized under Strong Nash Implementation. The second property, Weakly Pareto Nash Implementation (WPNI), requires that the least inefficient equilibrium Pareto dominates any other equilibrium. The egalitarian mechanism (EG), a variation of AC that meets individual rationality, and other asymmetric mechanisms are the only rules that meet WPNI and Individual Rationality. PNI and WPNI provide the first economic justification of the Price of Stability (PoS), a seemingly natural measure in the computer science literature but one not easily embraced in economics. EG minimizes the PoS across all individually rational mechanisms.

Keywords: Cost-sharing; Implementation; Average Cost; Egalitarian Mechanism (search for similar items in EconPapers)
JEL-codes: C70 C72 D71 D85 (search for similar items in EconPapers)
Pages: 44 pages
Date: 2012-02-01
New Economics Papers: this item is included in nep-gth, nep-mic and nep-net
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.economics.hawaii.edu/research/workingpapers/WP_12-3.pdf First version, 2012 (application/pdf)

Related works:
Journal Article: Implementing efficient graphs in connection networks (2013)
Working Paper: Implementing Efficient Graphs in Connection Networks (2011)
Working Paper: Implementing Efficient Graphs in Connection Networks (2010)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hai:wpaper:201203

Ordering information: This working paper can be ordered from
http://www.economics ... esearch/working.html

Access Statistics for this paper

More papers in Working Papers from University of Hawaii at Manoa, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Web Technician ().