P Dandekar, A Goel, MP Wellman, and B Wiedenbeck

ACM Transactions on Internet Technology 15(1): 3:1–3:41, 2015.


Credit networks are an abstraction for modeling trust among agents in a network. Agents who do not directly trust each other can transact through exchange of IOUs (obligations) along a chain of trust in the network. Credit networks are robust to intrusion, can enable transactions between strangers in exchange economies, and have the liquidity to support a high rate of transactions. We study the formation of such networks when agents strategically decide how much credit to extend each other. We find strong positive network formation results for the simplest theoretical model. When each agent trusts a fixed set of other agents and transacts directly only with those it trusts, all pure-strategy Nash equilibria are social optima. However, when we allow transactions over longer paths, the price of anarchy may be unbounded. On the positive side, when agents have a shared belief about the trustworthiness of each agent, simple greedy dynamics quickly converge to a star-shaped network, which is a social optimum. Similar star-like structures are found in equilibria of heuristic strategies found via simulation studies. In addition, we simulate environments where agents may have varying information about each others’ trustworthiness based on their distance in a social network. Empirical game analysis of these scenarios suggests that star structures arise only when defaults are relatively rare, and otherwise, credit tends to be issued over short social distances conforming to the locality of information. Overall, we find that networks formed by self-interested agents achieve a high fraction of available value, as long as this potential value is large enough to enable any network to form.

This substantially extends a paper with the same title that was presented at WWW-12:

Twenty-First International WWW Conference, pages 559-568, April 2012.

A preliminary version was presented at the IJCAI-11 Workshop on Trading Agent Design and Analysis, July 2011.


paper from ACM Digital Library