Mechanism Design on Trust Networks

Abstract:

We introduce the concept of a trust network -- a decentralized payment infrastructure in which payments are routed as IOUs between trusted entities. 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. Furthermore, this can be turned into an incentive compatible mechanism.