Mechanism design on trust networks

Arpita Ghosh, Mohammad Mahdian, Daniel M. Reeves, David M. Pennock, Ryan Fugger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations


We introduce the concept of a trust network - a decentralized payment infrastructure in which payments are routed as IOUs between trusted entities. The trust network has directed links between pairs of agents, with capacities that are related to the credit an agent is willing to extend another; payments may be routed between any two agents that are connected by a path in the network. The network structure introduces group budget constraints on the payments from a subset of agents to another on the trust network: this generalizes the notion of individually budget constrained bidders. We consider a multi-unit auction of identical items among bidders with unit demand, when the auctioneer and bidders are all nodes on a trust network. We define a generalized notion of social welfare for such budget-constrained bidders, and show that the winner determination problem under this notion of social welfare is NP-hard; however the flow structure in a trust network can be exploited to approximate the solution with a factor of 1 - 1/e. We then present a pricing scheme that leads to an incentive compatible, individually rational mechanism with feasible payments that respect the trust network's payment constraints and that maximizes the modified social welfare to within a factor 1 - 1/e.

Original languageEnglish (US)
Title of host publicationInternet and Network Economics - Third International Workshop, WINE 2007, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540771043
StatePublished - 2007
Externally publishedYes
Event3rd International Workshop on Internet and Network Economics, WINE 2007 - San Diego, CA, United States
Duration: Dec 12 2007Dec 14 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4858 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Workshop on Internet and Network Economics, WINE 2007
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Mechanism design on trust networks'. Together they form a unique fingerprint.

Cite this