Strategic Formation of Credit Networks – Swarthmore College

 

 

(cid:2)

(cid:2)

(cid:2)

(cid:2)

Strategic Formation of Credit Networks

PRANAV DANDEKAR, ASHISH GOEL, Stanford University
MICHAEL P. WELLMAN and BRYCE WIEDENBECK, University of Michigan

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.

Categories and Subject Descriptors: K.4.4 [Computing Milieux]: Electronic Commerce; J.4 [Computer
Applications]: Social and Behavioral Sciences—Economics

3

General Terms: Theory, Economics

Additional Key Words and Phrases: Trust, credit networks, strategic network formation, empirical game-
theoretic analysis

ACM Reference Format:
Dandekar, P., Goel, A., Wellman, M. P., and Wiedenbeck, B. 2015. Strategic formation of credit networks.
ACM Trans. Internet Technol. 15, 1, Article 3 (February 2015), 41 pages.
DOI:http://dx.doi.org/10.1145/2700058

1. INTRODUCTION
The study of strategic network formation seeks to understand the emergent behavior
and properties of a network when self-interested agents establish connections to one
another based on their local information. In general, establishing a connection incurs

Preliminary versions of parts of this work were presented at the 2011 Workshop on Trading Agent De-
sign and Analysis (TADA11), the 21st International World Wide Web Conference (WWW12), and the 50th
Allerton Conference on Communication, Control, and Computing.
This research was supported in part by NSF award IIS-0904325 and by the Army Research Laboratory
under Cooperative Agreement W911NF-09-2-0053.
Authors’ addresses: P. Dandekar (corresponding author), A. Goel, Department of Management Science and
Engineering, Stanford University, Stanford, CA; email: ppd@standford.edu; M. P. Wellman, B. Wiedenbeck,
Division of Computer Science and Engineering, University of Michigan, Ann Arbor, MI.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. Copyrights for components of this work owned
by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or repub-
lish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org.
c(cid:2) 2015 ACM 1533-5399/2015/02-ART3 $15.00
DOI:http://dx.doi.org/10.1145/2700058

ACM Transactions on Internet Technology, Vol. 15, No. 1, Article 3, Publication date: February 2015.

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

3:2

P. Dandekar et al.

u

w

u

w

c1

v

c2

p

p

c1 − p

v

c2 − p

(a) before the transaction

(b) after the transaction

Fig. 1. Updating credit to process a transaction between u and w worth p units.

a cost but also yields some benefit to connected agents. The agents are deemed to
be utility maximizing, that is, they make decisions in order to maximize the difference
between their total benefit and their total cost. This problem has been studied in many
different settings [Anshelevich and Hoefer 2012; Bala and Goyal 2000; Corbo et al.
2006; Fabrikant et al. 2003; Jackson and Wolinsky 1996]. One can ask interesting
questions about the emergent properties of the networks formed in each setting: What
network topologies are feasible in equilibrium? How do equilibrium networks differ
from socially optimal ones? How does this depend upon the cost of forming an edge and
the benefit derived from having a connection? If there are multiple equilibria, how can
agents select among them? This article is an investigation into some of these questions
in the context of credit networks, an abstraction for modeling trust among agents.

1.1. Credit Networks
Credit networks model trust in terms of one agent’s willingness to perform services
for another without immediate compensation. We interpret services broadly as any
activity, for example, completing a task or delivering a product, that is costly for the
provider and beneficial for the recipient. Performing a service incurs a reciprocal obli-
gation which may get discharged directly or indirectly in subsequent interactions. The
general idea is that the agents keep track of levels of trust as credit balances, and
update these balances as services are provided and obligations discharged.

A credit network represents these credit relationships through a directed graph with
edge capacities. Nodes in this graph correspond to agents, and edges correspond to
credit relationships between them. An edge of capacity c from node u to node v indi-
cates that agent u extends c units of credit to agent v, or equivalently, u is committed
to accept IOUs issued by v up to value c. These IOUs can be thought of as obligations,
denominated in the issuer’s private currency. It is possible that in the future v will
refuse to honor its outstanding obligations, in which case v’s currency becomes worth-
less and u gets stuck with irredeemable IOUs. The capacity c bounds u’s loss in this
eventuality, and therefore can be viewed as a measure of u’s trust in v.

Credit commitments between trusting nodes also enable remote transactions, as il-
lustrated in Figure 1. Say node w wants p units of service from node u. Nodes u and w
can transact—even though u does not directly trust w—via the trusted intermediary
v. Assuming p ≤ min{c1, c2}, the payment proceeds by w issuing an IOU to v worth p
units, and v issuing an IOU to u worth p units. If, however, p > min{c1, c2}, the trans-
action fails. As a result of a successful transaction, the credit capacities cuv and cvw
decrease by p, representing the remaining credit commitments. In addition, the capac-
ities cvu and cwv both increase to p from zero, since v and w will accept the return of
their own IOUs as payment.

Thus arbitrary payments can be routed through a credit network by passing IOUs
along a chain of trusting agents. Observe that routing payments in credit networks is
identical to routing residual flows in single-commodity flow networks. Also note that
payment flows in the opposite direction of credit, so a payment merely results in a

ACM Transactions on Internet Technology, Vol. 15, No. 1, Article 3, Publication date: February 2015.

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

Strategic Formation of Credit Networks

3:3

redistribution of credit: buyers expend credit, sellers gain it, and intermediaries ex-
change credit between their neighbors, with the total credit in the network unchanged.

1.1.1. Origins of the Model. The credit network model was invented independently by
(at least) four distinct groups of researchers motivated by somewhat different issues
and applications, but arriving at the same essential elements.

— DeFigueiredo and Barr [2005] sought a reputation system with bounded loss from

— Ghosh et al. [2007] aimed to support distributed payment and multi-user credit

coalitions of malicious users.

checking for multi-item auctions.

— Karlan et al. [2009] wanted to construct an economic model of informal borrowing

networks.

— Mislove et al. [2008] were concerned with deterring spam.

A common thread in the objectives of these researchers was to capture a notion of
pairwise trust, representable in quantified terms. In each case, the trust measure is
grounded by interpreting the quantity as a capacity for transaction. That is, the degree
of trust in one agent for another is measured by how much it is willing to expose itself
to transactions with that counterpart. In other words, the model operationalizes trust
as an extension of credit, in a framework where a credit balance entitles an agent to
transact with the agent granting credit. The common underlying credit model of these
four proposals was first noticed by Dandekar et al. [2011], who introduced the unifying
term “credit network” and its formal definition. By introducing suitable definitions of
transaction, credit networks can support a wide variety of applications. For example,
the inventors enumerated before interpret transactions, respectively, as obtaining ref-
erences guaranteeing good behavior [DeFigueiredo and Barr 2005], paying for auction
winnings [Ghosh et al. 2007], borrowing an asset [Karlan et al. 2009], and communicat-
ing messages [Mislove et al. 2008]. Subsequent authors proposed using this framework
to support networked asynchronous bilateral trading [Liu et al. 2010], and bartering
of tutorial services [Limpens and Gillet 2011].

1.1.2. Properties. Routing payments along chains of trust ensures that agents hold
IOUs issued only by other agents that they directly trust. As a result, if an agent de-
faults on its outstanding obligations, the only agents that incur a loss are those that
extended credit to the defaulting agent. Thus losses from default are localized. More-
over, the total loss incurred is bounded by the total credit extended to the defaulting
agent. These properties make credit networks robust against two attacks to which cen-
tralized currency systems are vulnerable: whitewashing [Friedman and Resnick 2001],
and Sybil attacks [Friedman et al. 2007]. Viswanath et al. [2012] argue that, in fact,
all reputation schemes designed for Sybil tolerance have essentially been versions of
the credit network idea. They propose an approximation to the max-flow calculation
that enables scalability to very large networks.

The effectiveness of credit networks in supporting distributed transactions was most
powerfully demonstrated by Dandekar et al. [2011]. Their analysis posits that nodes
repeatedly transact with each other according to a known probability distribution. In
particular, they showed analytically and via simulations that, for several classes of
graphs and with symmetric transaction probabilities, the long-term transaction failure
probability in credit networks is comparable to that in equivalent centralized currency
systems. Thus, in addition to being robust against attacks by malicious agents, credit

ACM Transactions on Internet Technology, Vol. 15, No. 1, Article 3, Publication date: February 2015.

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

3:4

P. Dandekar et al.

networks also provide a high degree of liquidity: the ability to sustain long sequences
of transactions.

1.2. Formation of Credit Networks
Extending credit to other agents increases liquidity in the network, enabling more
profitable transactions to go through. However, it also entails risk, since a counterparty
might default on its outstanding obligations. This raises the natural question: if agents
rationally weigh these risks and benefits, what kinds of networks will they form? In
order to use credit networks for practical applications, it is critical to understand the
structural and economic properties of the credit networks formed by strategic agents.
We address this question in this article.

1.2.1. Our Setting. Agents play a one-shot game where they determine how much
credit to extend other agents, and then engage in repeated probabilistic transactions
over the formed credit network. They derive value from successful transactions. Ex-
tending credit to other agents increases transaction success probability, thus contribut-
ing to utility. On the other hand, when an agent defaults, it imposes losses on its
creditors up to the amount of the credit it received. Thus, an agent’s net utility is its
total value from successful transactions minus the utility loss from extending credit to
untrustworthy agents. We study several variants of this game with different models of
risk, both analytically and through simulations. Our simulations employ an approach
known as empirical game-theoretic analysis (EGTA) [Wellman 2006].

We start with a model of dichotomous risk, where agents divide their counterparts
into fully trusted and untrusted categories. We assume the trust relation is symmet-
ric, and consider it as arising from a social network represented by an undirected
graph. Agents trust their neighbors in the social network and are willing to extend
them credit. They consider everyone else untrustworthy, and consequently never ex-
tend credit to non-neighbors. Though the strict dichotomy surely oversimplifies, it may
approximate reality for situations where dealing with strangers is particularly risky
(e.g., where identities are weak and norms of good behavior are poorly established). It
may also capture heuristic behavior of agents who are highly risk averse or especially
prize simplicity in social rules.

We also study a model of global risk, which represents an opposite extreme to the
dichotomous risk model. Under global risk, each agent has a publicly known proba-
bility of default. This model captures situations involving small, densely interacting
social groups, or where there are institutions such as credit-reporting agencies that
systematically gather and disseminate relevant risk information.

Finally, we study a model of graded risk that bridges the gap between global and
dichotomous risk. Under this model, agents are related on a social network, and each
agent has a private default probability. Agents receive noisy signals about each other’s
probability of defaulting, and these signals are more informative for neighbors in the
social network.

1.2.2. Our Results.

Dichotomous Risk. Under dichotomous risk, when we allow only bilateral transac-
tions (i.e., transactions only between adjacent nodes in the social network, and pay-
ments routed only along the direct edge between nodes), we show that the formation
game is a potential game (Theorem 3.2). This implies that best-response dynamics
always converge to a pure-strategy Nash equilibrium (PSNE). Moreover, for a large,

ACM Transactions on Internet Technology, Vol. 15, No. 1, Article 3, Publication date: February 2015.

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

Strategic Formation of Credit Networks

3:5

natural class of transaction size distributions, we show that agents’ utilities are con-
cave in their credit allocations. This allows us to prove that every Nash equilibrium of
the game maximizes social welfare (Theorem 3.3). We further show that the credit net-
works generated by any two PSNE are cycle reachable from each other (Theorem 3.5),
which means that they support the same sequences of transactions [Dandekar et al.
2011].

With non-bilateral transactions, the game becomes significantly less well behaved:
it may not admit a PSNE (Theorem 3.8), and even when it does, the price of anarchy
(PoA) can be unbounded (Theorem 3.9).

Global Risk. Under global risk, we analyze several scenarios. First, we investigate
PoA and the structure of equilibria when each agent is limited to extend credit to at
most one other agent. We prove that, if we disallow the empty network as an outcome,
the PoA of the formation game is unbounded (Theorem 4.4), even though all PSNE net-
works have a star-like structure (Theorem 4.3). Instead we focus on the structure of
equilibria under two simple dynamics: sequential arrival and greedy dynamics. When
nodes arrive sequentially and create a single link, we show that a node u always ex-
tends credit to either the node v that arrived immediately before u or to the node
to which v extends credit (Theorem 4.6). Thus the resulting network has a comb-like
structure. Under greedy dynamics, nodes extend their entire credit budget to the node
that has the lowest risk of default. If the default probabilities are all distinct, this re-
sults in a star-like network structure, which is also the optimal structure in terms of
social welfare (Theorem 4.5). Thus, even though the PoA can be unbounded, nodes can
easily find the optimal network using greedy dynamics.

We also use empirical game-theoretic simulations to investigate a richer model of
global risk in which agents are not constrained to a single link or a fixed budget, and
transaction probabilities and values may be asymmetric. Under global risk, we find
star-like equilibrium networks under all conditions, but settings with high default
rates or low transaction surpluses also have empty network equilibria. In addition,
when default rates are low, transaction-dependent credit-issuing strategies can appear
in equilibrium.

Graded Risk. We address graded risk exclusively through empirical game simula-
tions. In this setting, the star-like equilibria disappear, highlighting the importance
of ensuring that central nodes are unlikely to default. Empty network equilibria are
present for exactly the same settings as under global risk, indicating that the condi-
tions under which agents issue no credit may not depend as strongly on the informa-
tion structure. Transaction-dependent equilibria arise under the same conditions as
for global risk as well as those with high transaction surplus.

Summary and Key Insights. The theoretical analyses demonstrate generally how
network formation depends on environmental conditions. We get strong positive re-
sults for dichotomous risk and symmetric bilateral transactions but, once we allow
transactions on paths, the worst-case network formation performance becomes arbi-
trarily bad. Our simulation-based analysis therefore investigates how credit network
formation by self-interested agents might play out in representative, less technically
constrained environments. The results confirm that the worst case indeed cannot be
avoided in that networks may simply fail to form if the benefits are not sufficiently
large. On the other hand, we find that when the potential value of the network is large,
self-interested agents will pursue strategies that lead to networks that achieve the

ACM Transactions on Internet Technology, Vol. 15, No. 1, Article 3, Publication date: February 2015.

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

3:6

P. Dandekar et al.

lion’s share of this benefit. In other words, in complex environments it is too much to
expect perfect network formation or even guaranteed lower bounds on relative perfor-
mance, but when demand for profitable transactions is present, self-interested agents
will form viable credit networks.

1.2.3. Comparison to Other Network Formation Games. The various models of strategic
credit network formation that we analyze relate to an extensive literature on net-
work creation games. Our simplest model, with dichotomous risk and bilateral trans-
actions, can be viewed as a special case of a network contribution game as defined by
Anshelevich and Hoefer [2012]. In a network contribution game, agents allocate a
budget of effort among their neighbors and receive a reward for each link that is in-
creasing in the sum of their effort and their neighbor’s. The authors state a result
that generalizes Theorem 3.2 but otherwise focus on bilateral link creation models.
Because credit edges are by nature directed, our analysis of this game focuses on the
implications of equilibria under unilateral deviations.

When we lift the constraint of bilateral transactions, path lengths become a relevant
strategic consideration. Fabrikant et al. [2003] studied a model where agents benefit
from reducing their distance to others in the network. In their network creation games,
agents incur costs for creating edges and also for the sum of their distances to all other
nodes. In a credit network, agents care about the existence and the capacity of paths,
as well as the likelihood of neighbors defaulting. In both the global and graded risk
settings, our results depend more strongly on considerations of default risk than on
distance between nodes.

Network formation in the presence of risk was studied by Blume et al. [2011] in a
model motivated by financial contagion and epidemic diseases. In their setting, nodes
derive utility only from direct edges, whereas risk is contagious (i.e., failure of distant
nodes is also a source of risk). The credit network model flips this: nodes derive benefit
from transactions along direct as well as multihop paths, whereas only direct edges
are sources of risk.

2. MODEL AND DEFINITIONS
Let V denote the set of n agents, and equivalently, the n nodes of the formed credit
network.1

2.1. Game Model
Agents play a one-shot game where they choose credit allocations to form an initial
network G. An edge from node u to node v of capacity cuv(G) represents the credit
extended by agent u to agent v in the network G. Thus G is a directed graph with
edge capacities. Agents choose how much credit to extend to whom based on public
or private information about transactions (Section 2.2), as well as the default risk of
other agents (Section 2.4). The credit agent u offers may be constrained by a budget
Bu ≥ 0, representing the total credit that u can extend to other agents.

A strategy for agent u is a mapping of u’s public and private information to a feasible
credit allocation {cuv(G), v ∈ V : cuv(G) ≥ 0 and
v∈V cuv(G) ≤ Bu}. The combination
of agent strategies applied to the given information induces the initial network G. The
payoff to agent u is determined by the transactions and defaults that play out on the
network starting from G, according to the models described next.

(cid:2)

1These and other symbols employed in the article are summarized in the appendix, Table III.

ACM Transactions on Internet Technology, Vol. 15, No. 1, Article 3, Publication date: February 2015.

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

Strategic Formation of Credit Networks

3:7

2.2. Transaction Model
Once a network G is formed, agents engage in a sequence of transactions with each
other. Following prior work [Dandekar et al. 2011], transactions are generated accord-
ing to a stochastic process. At each time step t = 1, 2, . . . , a pair of transacting agents
(cid:6)u, v(cid:7), with u being the payer (buyer) and v the payee (seller), is chosen with proba-
bility λuv. The transaction rate matrix (cid:3) = {λuv : u, v ∈ V} is public and satisfies the
following properties: (i) λuu = 0, (ii) λuv ≥ 0, and (iii)

u,v λuv = 1.

Suppose agents (cid:6)u, v(cid:7) are chosen to transact at time t. Then the transaction size
uv between u and v is drawn from a transaction size distribution over [ 0, ∞) with a
xt
probability density function (pdf) Xuv(·) and a corresponding cumulative distribution
function (cdf) Xuv(·). We assume that the pdfs Xuv(·) are public. Let X := {Xuv(·) : u,
v ∈ V} be the pdf matrix.

(cid:2)

In the general credit network framework, transaction payments may be routed as
a flow over multiple paths. For all the settings considered in this article (bilateral or
single-unit transactions, defined shortly), it is sufficient to route payment over a single
path. Given a transaction size x, a feasible path in the network G from node v to node
u is a set of directed edges P = {(v, u1), (u1, u2), . . . , (uk−1, uk), (uk, u)} such that for
all (w, y) ∈ P, cwy(G) ≥ x. We route payments along the shortest feasible path in the
network. Let P t
vu be the shortest feasible path in the credit network from v to u at
time t. A successful transaction of size xt
uv results in a change of credit capacities along
edges in P t
vu as follows. Let Gt denote the state of the network G at time t = 0, 1, 2, . . . ,
where G0 = G. Then, for w, y ∈ V and a successful transaction at time t > 0,

⎧
⎨

⎩

cwy(Gt) =

cwy(Gt−1) − xt
cwy(Gt−1) + xt

uv,
uv,

if (w, y) ∈ P t−1
vu
if (y, w) ∈ P t−1
vu

.

cwy(Gt−1), otherwise

So, in order for a payment xt
uv from u to v to succeed, there must exist a feasible path
in the credit network from the payee v to the payer u. If no such path exists, the
transaction fails, in which case all credit capacities remain unchanged. Thus, for all
t > 0 and for all u, v ∈ V, cuv(Gt) + cvu(Gt) = cuv(G) + cvu(G).

The repeated probabilistic transactions induce a Markov chain over the states of the
network, which we denote by M(G, (cid:3), X). A transaction regime is defined as the tuple
(cid:6)(cid:3), X(cid:7). We say a transaction regime (cid:6)(cid:3), X(cid:7) is symmetric if the transaction rate matrix
(cid:3) is symmetric, that is, for all nodes u, v ∈ V, λuv = λvu, and that the transaction
size pdfs are symmetric, that is, for all u, v ∈ V, Xuv(·) = Xvu(·). For most of the analy-
sis, we consider symmetric transaction regimes where, additionally, the Markov chain
is ergodic.

2.3. Utility
Agents choose credit allocations to maximize their utility. Agents derive value from suc-
cessful transactions, but they risk loss of utility when they extend credit to potentially
untrustworthy agents. We model this risk in several ways, but can generally denote
the expected loss of utility to u associated with the prospect of default by v by (cid:4)uv(G),
with the constraints that (cid:4)uv(G) ≥ 0 and (cid:4)uv(G) > 0 only if cuv(G) > 0.

In our analytical treatments (Sections 3 and 4), we assume that transaction val-
ues are uniform across (u, v) pairs. We can therefore define the value derived from
transactions as proportional to the steady-state success probability of all transactions
where the agent is a payer. Let puv(G) be the steady-state success probability of the

ACM Transactions on Internet Technology, Vol. 15, No. 1, Article 3, Publication date: February 2015.

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

(cid:2)

3:8

P. Dandekar et al.

transactions from u to v (i.e., where u is the payer) when the initial network is G. Then,
the total utility of an agent u when the initial network is G is given by

Uu(G) = γ

puw(G) −

(cid:4)uv(G),

(1)

(cid:6)

w∈V

(cid:6)

v∈V:cuv(G)>0

where γ is a constant that converts transaction success probability into equivalent
utility units. The overall social welfare in network G is simply the sum of utilities of
all nodes in G: U(G) :=

(cid:2)

u∈V Uu(G).

It is difficult to characterize the steady-state transaction success probabilities for
arbitrary networks and transaction regimes. However, for the settings we analyze, we
are able to exploit results established by Dandekar et al. [2011].

2.4. Risk Model
In order to model variation in (cid:4)uv(G), we assume the agents are embedded in an
exogenously defined social network represented by a simple undirected graph H =
(V, E). The social network H influences how (cid:4)uv(G) for an agent u varies across agents
v ∈ V. We consider three specific models of how risk changes as a function of distance
between u and v in H.

2.4.1. Dichotomous Risk. In this model, an agent u partitions the set of other agents
according to whether they are neighbors or non-neighbors in H. For network G, agent
u estimates risk exposure to be

(cid:7)

(cid:4)uv(G) =

if (u, v) ∈ E

0,
∞, otherwise

.

(2)

This model assumes agents are willing to interact only with their neighbors in H. For
any credit network G formed under this model, cuv(G) = 0 if (u, v) /∈ E.

2.4.2. Global Risk. In this model, we assume that each agent v has a default probability
δv ∈ (0, 1] which is public. If v defaults, a node u that extended credit cuv(G) to v loses
cuv(G) units. Thus (cid:4)uv(G) = δvcuv(G).

2.4.3. Graded Risk. Here, as in the global risk model, each agent v has default prob-
ability δv, but this information is not publicly known. Instead, each agent u receives
a signal δuv about the default probability of each other agent v. These signals are
decreasingly informative with distance in H, so agents know much more about the de-
fault probabilities of their neighbors in the social network than about distant nodes.
In our simulations, we implement this by drawing agents’ default probabilities from a
beta distribution δv ∼ Beta(α, β). Agent u then receives a signal in the form of some
number of samples ∂uv drawn from the binomial distribution on δv, where ∂uv decreases
exponentially with social network distance. Given this form of evidence, the posterior
is also beta distributed. Specifically, if u’s sample for v includes ˆd defaults, then its
posterior default probability is (α + ˆd)/(α + β + ∂uv).

3. NETWORK FORMATION UNDER DICHOTOMOUS RISK
Recall that under dichotomous risk, (cid:4)uv(G) is defined by (2); as a result nodes extend
credit only to their neighbors in H.

ACM Transactions on Internet Technology, Vol. 15, No. 1, Article 3, Publication date: February 2015.

(cid:2)

(cid:2)

(cid:2)

(cid:2)