A Market Clearing Solution for Social Lending

1 Introduction

Social lending, or peer-to-peer lending, which allows individuals to lend and borrow money to each other directly without the participation of banks, is an exploding business on the Internet: the total amount of money borrowed using such peerto-peer loans was approximately $650 million in 2007, and is projected to reach $5.8 billion by 2010.

The social lending market consists of borrowers seeking some target loan amount (their demand), and lenders seeking to invest some fixed amount of money in loans (their budget). Lenders usually prefer to invest their budget in multiple borrowers' loans to spread risk from defaulting borrowers, and each borrower's loan is also usually funded by multiple lenders. Borrowers are 'non-homogeneous'- different borrowers have different characteristics such as credit rating and desired loan length, and command different interest rates based on their creditworthiness. That is, different borrowers correspond to investments with different risk-return profiles. As a result, lenders have preferences over which borrowers We now have a large two-sided matching market where agents on both sides have multiunit capacities, and preferences - lenders have preference rankings (possibly with ties) over the set of acceptable borrowers they're willing to lend to, and borrowers have preferences over lenders based on their offered interest rates. But the preferences of all these agents may be conflicting - many lenders may compete to lend to the same borrower who is their common top choice, while this borrower's preference might be an entirely different lender who offers him a lower interest rate, who in turn has a different top borrower choice. Clearly, it need not be possible to make all agents simultaneously happy, raising the natural question of what constitutes a 'good' assignment. In this paper, we investigate the social lending market from a computational social choice perspective: what is a fair and efficient way to clear this marketplace, and how can it be computed?

Our contributions. We present a model (§2) for the social lending marketplace based on Zopa (www.zopa.com), which, with over 400, 000 members and £100 million in its markets and over £100000 traded each day, is the first and among the largest social lending sites on the Web.

We first address the question of what is a desirable allocation in the social lending market in §3, and argue that an allocation that is stable, Pareto efficient, fair amongst 'equal' borrowers, and also addresses the need for risk diversification to reduce default risk is a desirable solution concept in this market. We then address the question of finding an algorithm that returns such an allocation in §4.

When preference lists contain ties, as in our social lending context, not all stable matchings are Pareto efficient. The question of how to find a Pareto-stable matching when preferences contain ties has recently been addressed for the many-to-one matching model in [Erdil and Ergin, 2008; 2009]. A naive adaptation of this algorithm to our many-tomany market returns a Pareto-stable assignment in time that scales with the total capacity of all nodes in the graph, i.e., the amount of money traded in the market, requiring us to develop a new algorithmic approach. We design a strongly polynomial time algorithm for computing a Pareto-stable outcome in a many-to-many matching market with indifferences, and apply it to a reduced marketplace where 'identical' borrowers are grouped into equivalent classes or 'categories'; we then reallocate amongst categories to achieve fairness amongst borrowers and risk diversification. The overall runtime is polynomial in the number of lenders and the number of borrower categories, which is a small constant (=10) for the Zopa marketplace.

Related work. Social lending is a relatively new application that has only recently begun to be addressed in the research literature, starting with the work in [Freedman and Jin, 2009] on default rates. Most of the research on social lending takes an empirical approach as in [Freedman and Jin, 2009]; [Chen et al., 2009] analyzes the auction held for a single borrower's loan in the Prosper market, but does not address the several coexisting lenders and borrowers in the marketplace. To the best of our knowledge, social lending has not been studied much from a marketplace design or social choice perspective.

There is a very vast literature on two-sided matching markets and stable matching; for a review of the economics literature on the subject, see [Roth and Sotomayor, 1992; Roth, 2008]; for an introduction to the computer science literature addressing algorithmic and computational questions, see, e.g., [Gusfield and Irving, 1989; Iwama and Miyazaki, 2008]. The paper most relevant to our work from the stable matching literature is [Erdil and Ergin, 2008; 2009], who study the algorithmic question of finding Paretostable matchings for a many-to-one matching market; see §4. The many-to-many setting is far less well studied in the stable matching literature, and focuses largely on structural results in settings without indifferences; see, e.g., [Hatfield and Kominers, 2010; Echenique and Oviedo, 2006].

2 A Lending Market Model

We model the social lending marketplace M as a bipartite graph with nodes (A, B) and edges E. The nodes in A represent the lenders and the nodes in B are the borrowers. Nodes on both sides have multiunit capacities: a lender i's capacity ci is her budget, the total amount of money she wants to lend. A borrower j's capacity cj is his demand, the total loan amount he wants to borrow. We will assume that the capacities are integers by expressing them in the smallest unit of currency. The edge set E of M is the set of pairs (i, j) where lender i is willing to lend to borrower j.

Each lender specifies the interest rates at which she is willing to lend money to different acceptable borrowers; as in Zopa, this is the actual interest-rate that she will receive on any loans to that borrower. Note that each lender can offer different interest rates to different borrowers, and the same borrower can be offered different interest rates by different lenders.

Every acceptable borrower, along with the specified interest rate, represents a possible investment for the lender, with a particular risk-return profile. Each lender has a preference list Pi ranking the investments corresponding to these borrowerinterest rate pairs, i.e., its neighbors {j ∈ B : (i, j) ∈ E}.

These preferences need not be strict and the lender can be indifferent between, i.e., equally prefer, two different investments; that is, preference lists can have ties. Since the preference list is restricted to i's neighbors (i.e., acceptable borrowers), it is naturally incomplete. (As an example, lender i's preferences, denoted Pi = ([j1, j2], [j3, j4, j5]), could be as follows: i is indifferent between j1 and j2, and prefers both of them to j3, j4, j5 among all of whom i is indifferent; she finds all other borrowers unacceptable.) In general, a lender can also have preferences over sets of investments; however, here we will restrict ourselves to expressing preferences over individual investments for simplicity 1 .

Each borrower j has an implicit preference ranking Pj over lenders based on the interest rates they offer him: j prefers lenders in non-increasing order of offered interest rates, and is indifferent amongst lenders who offer him the same interestrate (so borrowers' preferences Pj can contain ties as well).

We partition the set of borrowers into equivalence classes, or categories C = {C1, . . . , Cm}: two borrowers are equivalent, i.e., belong to the same category, if no lender can distinguish between them based on the information available about them in the marketplace. Thus, all lenders are indifferent between the borrowers in a category, and offer them the same interest-rate. This also means that borrowers in a category all have the same preferences over lenders, and that a lender's preference list need only rank categories, not individual borrowers. The number of categories can be as large as the number of borrowers when personal information is provided by/about each borrower (as in Prosper), or very small when the only information revealed is the credit-rating and loan length (as in Zopa, which only allows lenders to specify interest rates for 10 borrower categories).

Diversification to decrease default risk is a very important factor in social lending. Instead of modeling this into the preferences of lenders, we deal with it as Zopa-Zopa breaks up each lender's budget into small sums each of which is lent to a different borrower to diversify risk, so we will similarly ensure that each lender's budget is uniformly spread amongst many different borrowers in the final allocation.

We note that we do not model reserve rates, nor the dynamic aspect of the social lending market in this work.

Feasible assignments. The output of the market is a multiunit pairing, or assignment X = (xij )(i,j)∈E between A and B, where xij ∈ N∪{0} is the number of units assigned from i ∈ A to j ∈ B (when ci = cj = 1 for all nodes, an assignment reduces to a matching). An assignment X is feasible if it simply satisfies capacity constraints on both sides, i.e., ∑j xij ≤ ci and ∑i xij ≤ cj. Note that the preferences Pi, Pj do not matter to the feasibility of an assignment.

3 What Is a Good Outcome?

Having defined the set of feasible assignments, how do we choose one from amongst the very large number of possible assignments? An ideal solution concept for the social lending market would be Pareto efficient, fair - both across lenders and borrowers, as well as amongst similar borrowers - exist for every instance of the input, and be efficiently computable (since social lending markets transact huge amounts of money, it should be implementable in time that depends only on the number of agents, not on the money being traded in the marketplace). What assignment has these properties?

1 This is both for technical tractability and to avoid eliciting complex combinatorial preferences from lenders.

A very widely used solution concept in two-sided matching markets is that of stability [Gale and Shapley, 1962]: there is no pair of individuals that both strictly prefer each other to some partner they are currently assigned to (such a pair would be called a blocking pair). Stability can be interpreted as a notion of fairness in our context - while it is not possible to guarantee each lender her most preferred allocation, a stable allocation is fair in the sense that if a lender indeed sees a better allocation, that allocation does not also 'prefer' her in return. However, when preference lists contain ties as in our case, it is well-known that stable matchings need not be Pareto efficient, even when all nodes have unit capacity; see [Roth and Sotomayor, 1992].

Therefore, we will need to explicitly require that the solution is both stable and Pareto efficient; such assignments are called Pareto-stable assignments [Sotomayor, 2009]. However, as the next example shows, applying the concept of Pareto stability directly to the marketplace M may not produce very desirable solutions: a solution may well be Paretostable, but hand out very different interest rates to two identical borrowers, violating our fairness requirement.

Example 3.1. There are two lenders i1, i2 and two borrowers j1, j2 with two units of supply/demand each. Both lenders are indifferent between the two borrowers; the first lender i1 offers 7% to both borrowers, and the second lender i2 offers 15% to both borrowers. The matching where i1 lends both units to j1 (at 7%), and i2 lends both units to j2 (at 15%) is stable and also Pareto efficient. However, the matching where both lenders lend one unit to each borrower is also Paretostable and 'more fair' since both j1 and j2 get equal amounts of the low and high interest rates (note that this matching does not Pareto-improve the previous matching since it makes j1 strictly worse off). In addition, each lender spreads her loan across more borrowers, so diversity improves as well.

This example illustrates that we cannot simply apply the solution concept of Pareto stability directly to the social lending marketplace M. Instead, we will consider a modified market, where the lender side is unchanged but borrowers are aggregated by category into 'meta-borrowers', with demand equal to the aggregate demand of that category (recall that a category can consist of a single borrower, when there is plenty of information about borrowers in the marketplace). We will first find a Pareto-stable assignment in this reduced marketplace- how to find such an assignment is the key technical problem we need to solve- and then distribute each lender's allocation to a meta-borrower amongst all the borrowers in that category to ensure envy-freeness amongst them.

We note that another natural solution concept, maximum size assignment (i.e., the one with the largest trade volume), is unsuitable here since it ignores all agents' preferences; it is also NP-hard to compute [Iwama et al., 1999]. However, it is easy to show that the size of any stable assignment (and therefore also our assignment) is at least half the size of the maximum size assignment.

The assignment we propose to clear the social lending market is the following.

MARKET CLEARING ASSIGNMENT: Given a lending market M = (A, B) with categories C = {C1, . . . , Cm}:

1. Create ameta-borrower for each categoryCr with demand ∑j∈Cr cj, and the same preferences as those of borrowers in Cr. Denote the resulting market by (A, C).
2. Compute a Pareto-stable assignment X∗ = (x∗iCr ) for (A,C), where x∗iCr is lender i's total investment in category Cr (§4).
3. Assign each lender's investment x∗iCr across all borrowers in category Cr to ensure diversity and envy-freeness; denote the final assignment by Y = (yij) (§4).

We have the following result about this assignment.

Theorem 3.2 (Main). The final assignment Y = (yij) can be computed in time O(|A|4 + |A||B|) and has the following properties:

1. Stability: There are no blocking pairs in the original marketplace M = (A, B).
2. Pareto efficiency: No agent in M can be made better off without making some other agent in M strictly worse off.
3. (Weak) envy-freeness: No borrower envies the allocation of any other borrower in its category.
4. Diversity: Given the allocations X ∗ = (x∗iCr ), each lender i spreads her budget amongst the maximum number of distinct borrowers.

4 Algorithm

We will first address the problem of efficiently finding a Pareto stable assignment in an abstract two-sided manyto-many matching market with separable responsive preferences, and then apply the algorithm we develop to the modified marketplace with lenders and meta-borrowers.

We begin with some formal definitions. Recall that we have a two-sided matching market M = (A,B) with preference lists Pk and multi-unit capacities ck for all agents k, and k's preference over sets is the natural (partial) order defined by the preferences Pk over individuals as in [Erdil and Ergin, 2008; 2009]. We can assume without loss of generality that |A| = |B| = n by adding dummy isolated nodes with ck = 0 to the market.

Definition 4.1 (Level function). We use the function Li(·) to encode the preference list of a node i ∈ A. For each j ∈ Pi, let Li(j) ∈ {1, . . . , n} denote the ranking of j in i's preference list. Therefore, for any j, j ′ ∈ Pi, if Li(j) < Li(j ′ ), then i strictly prefers j to j ′ ; if Li(j) ≤ Li(j ′ ), then i weakly prefers j to j ′ ; if Li(j) = Li(j ′ ), then i is indifferent between j and j ′ . The definition of the level function Lj(·) for each j ∈ B is symmetric.

Stability. We say that an assignment X = (xij) is stable if there is no blocking pair (i, j), i ∈ A and j ∈ B, (i, j) ∈ E, such that both i and j have leftover capacity; or i has leftover capacity and there is i′ , xi′ j > 0, such that j strictly prefers i to i′ (or similarly for some j); or there are i′ and j ′ , xij′ > 0 and xi′ j > 0, such that i strictly prefers j to j ′ and j strictly prefers i to i′ . Note that both members of a blocking pair must strictly prefer to trade with each other. A stable assignment always exists, and can be found (efficiently) using a variant of Gale-Shapley algorithm [Gale and Shapley, 1962] for computing stable matchings.

Pareto efficiency. Given an assignment X = (xij), let xi(α) = ∑j: Li(j)≤α xij be the number of units of i's capacity that is assigned at levels no worse than α, and xj(β) = ∑i: Lj(i)≤β xij be the number of units of j's capacity that is assigned at levels no worse than β. We say that X is Pareto efficient if there is no other feasible assignment Y = (yij) such that yi(α) ≥ xi(α) and yj(β) ≥ xj(β), for all i, j and α, β, and at least one of the inequalities is strict. That is, X is not Pareto-dominated by any other assignment where at least one agent is strictly better off and no one is worse off.

Pareto stability. A feasible assignment is called Paretostable if it is both stable and Pareto efficient.

Recall that when preference lists contain ties, a stable matching need not be Pareto efficient. The following definition is critical to our algorithm for Pareto-stable assignment.

Definition 4.2 (Augmenting Path and Cycle). Given an assignment X = (xij), a sequence [i0, j1, i1, . . . , jℓ, iℓ, jℓ+1] is an augmenting path if the following conditions hold:

• xi0 < ci0 and xjℓ+1 < cjℓ+1 .
• xikjk > 0 for k = 1, . . . , ℓ.
• Lik (jk) ≥ Lik (jk+1) and Ljk (ik-1) ≤ Ljk (ik) for k = 1, . . . , ℓ.

A sequence [i1, j2, i2, . . . , jℓ, iℓ, j1, i1] is an augmenting cycle if the following conditions hold:

• xikjk > 0 for k = 1, . . . , ℓ.
• Lik (jk) ≥ Lik (jk+1) and Ljk (ik-1) ≤ Ljk (ik) for k = 1, . . . , ℓ, where i0 = iℓ and jℓ+1 = j1.
• At least one of these inequalities is strict. If ik is such a node, we say the augmenting cycle is associated with ik at level Lik (jk) (and similarly for jk.)

Since our nodes have preferences in addition to capacities, augmenting paths and cycles must improve not just the size of an assignment but also its quality, as given by node preferences. The first condition in the definition of the augmenting path says that the capacities of i0 and jℓ+1 are not exhausted. The second condition says that there is a positive allocation from ik to jk in the current assignment X, and the last condition says that ik weakly prefers jk+1 to jk and jk weakly prefers ik-1 to ik. Thus, we can inject (at least) one unit of flow from ik-1 to jk and from iℓ to jℓ+1 and withdraw the same amount from ik to jk for each k = 1, . . . , ℓ in the augmenting path to obtain a Pareto improvement over X. A similar Pareto improvement can be obtained for augmenting cycles.

We have the following easy lemma.

Lemma 4.3. Any feasible assignment X that has no augmenting paths or cycles is Pareto efficient.

4.1 Computing a Pareto Stable Assignment

We now give a strongly polynomial time algorithm to compute a Pareto stable assignment. Note that if X is a stable assignment, reassigning according to any augmenting path or cycle of X preserves stability, i.e., any assignment Y that Pareto-dominates a stable assignment X is stable as well [Erdil and Ergin, 2009]. Together with Lemma 4.3, this suggests that starting with a stable assignment, and then making improvements to it using augmenting paths and cycles until no more improvements are possible, will result in a Paretostable assignment.

How do we find such augmenting paths and cycles? First consider the simplest case with unit capacity, i.e., ci = cj = 1 for all i, j, where an assignment degenerates to a matching. Given an existing matching, define a new directed bipartite graph with the same nodes, where all forward edges are "weak improvement" edges with respect to the existing matching, and backward edges correspond to the pairings in current matching. Then we can find augmenting paths by introducing a source s and sink t that link to unmatched nodes on each side and finding s-t paths in the resulting network. Augmenting cycles can be found by a similar construction.

For our general case where ci, cj ≥ 1, however, even the concept of improvement edges for a node is not well defined: since a node can have multiple partners in an assignment, a particular edge can be an improvement for some part of that node's capacity and not for some others. For instance, suppose that node i (with ci = 2) is matched to nodes j1 and j3, and suppose that i strictly prefers j1 to j2 to j3. Then, (i, j2) would only represent an improvement relative to (i, j3), but not with respect to (i, j1), both of which exist in the current assignment. An obvious way to fix this problem is to make copies of each node, one copy for each unit of its capacity, in which case improvement edges are well-defined - each unit of capacity is associated with a unique neighbor in any assignment. However, this new graph has size ∑i ci + ∑j cj, leading to a runtime that is polynomial in ∑i ci + ∑j cj, which is exponential in the size of the input.

Construction of networks. In order to define improvement edges in this setting with multiunit capacities, we will create a new augmented bipartite graph G from the original bipartite market M and the preference lists Pk. The vertex set of G will consist of copies of each node in M, where each copy represents a level on that node's preference list. We then define forward and backward edges between the vertices: forward edges are the (weak) improvement edges, while there is one backward edge for every edge (i, j) ∈ E corresponding to i and j's levels in Pj and Pi. This augmented graph, which is assignment-independent and depends only on the preference lists of the nodes, is then used to define a sequence of networks with assignment-dependent capacities which we will use to find augmenting paths and cycles.

Definition 4.4. Given the market M, construct G as follows.

• Vertices: For each node i ∈ A ∪ B, we introduce n new vertices T(i) = {i(1), . . . , i(n)}, where i(α) cor-

responds to the α-th level of the preference list of i. (If i has k < n levels in his preference list, it suffices to introduce k vertices i(1), . . . , i(k); here, we use n levels for uniformity.)

• Edges: For each pair (i, j) ∈ E, let α = Li(j) and β = Lj(i). We add a backward edge between i(α) and j(β), i.e., j(β) → i(α). Further, we add a forward edge i(α′ ) → j(β′ ) for every pair of vertices i(α′ ) and j(β′ ) satisfying α′ ≥ α and β′ ≥ β.

Figure 1 gives an example of the construction of graph G, when M contains two lenders i1, i2 and three borrowers j1, j2, j3 (node preferences are specified next to each node in the top figure, e.g., i2 is indifferent between j1 and j2, and prefers both of them to j3). The figure on the right illustrates the vertices T(·) of G and the backward edges; the figure on the bottom left shows the forward edges between the two groups of vertices T (i2) and T (j3) in G.

Note that the construction of G is completely independent of any actual assignment X. We next define the networks H,Hi,α,Hj,β, whose structure is based on G and is assignment-independent, but whose edge capacities depend on the assignment X.

Definition 4.5 (Network H, Hi,α and Hj,β). Given the graph G and an assignment X = (xij), let G(X) be the network where all forward edges in G are assigned capacity ∞, and all backward edges are assigned capacity xij . We use G(X) to define the networks H(X), Hi,α(X) and Hj,β(X) for each i ∈ A and j ∈ B, and α, β = 1, . . . , n, as follows.

For H(X), include a source s and a sink t; further, for each i ∈ A and j ∈ B, add an extra vertex hi and hj , respectively. Connect s → hi with capacity ci-xi, and hj → t with capacity cj -xj , where xi = ∑j xij and xj = ∑i xij . Further, connect hi → i(α) with capacity ∞ for α = 1, . . . , n, and connect j(β) → hj with ∞ capacity for β = 1, . . . , n.

For Hi,α(X), we add a source s and a sink t, and connect s → j(β) with capacity ∞ for each vertex j(β) satisfying α > Li(j) and β ≥ Lj(i). Further, we connect j(β) → t with capacity xij for each j(β) satisfying α ≤ Li(j) and β = Lj(i). The network Hj,β(X) is defined symmetrically.

We will use the network H to find augmenting paths with respect to an existing stable assignment X. Observe that the only edges from the source with nonzero capacity are those that connect to a node i ∈ A with leftover capacity; similarly, the only edges to the sink with nonzero capacity are from a node j ∈ B with leftover capacity. Sending flow from s to t in H therefore involves increasing the total size of the assignment while maintaining quality, exactly as in an augmenting path for X. Similarly, we will use the networks Hi,α and Hj,β to find augmenting cycles associated with i and j at level α and β respectively. Consider any flow from s to t in Hi,α, say,

We know that α > Li(j1) (i.e., i strictly prefers j1 to all its neighbors at level α) and Lj1 (i1) = β1 ≥ Lj1 (i) (i.e., j1 weakly prefers i to i1). Further, we have α ≤ Li(j2) (this implies that i strictly prefers j1 to j2) and Lj2 (i2) ≤ β2 = Lj2 (i) (i.e., j2 weakly prefers i2 to i). That is, flows from s to t in Hi,α correspond to augmenting cycles for node i at levels less than or equal to α in X (and similarly for Hj,β).

Our algorithm, summarized below, finds maximum flows in all the constructed networks H, Hi,α and Hj,β to eliminate augmenting paths and cycles.

PARETO STABLE ASSIGNMENT (ALG-PS)

1. Let X be an arbitrary stable assignment
2. Construct networks H(X), Hi,α(X) and Hj,β(X), for each i ∈ A, j ∈ B, and α, β = 1, . . . , n
3. For H, Hi,α and Hj,β constructed above (H to be executed first)
4. (a) Compute a maximum flow F = (fuv) from s to t (if there is no flow from vertex u to v, set fuv = 0)
5. (b) For each forward edge i(α) → j(β), let xij = xij + fi(α)j(β)
6. (c) For each backward edge j(β) → i(α),
7. let xij = xij - fj(β)i(α)
8. (d) If the graph is Hi,α
9. Let xij = xij + fsj(β) for each s → j(β)
10. Let xij = xij - fj(β)t for each j(β) → t
11. (e) If the graph is Hj,β
12. Let xij = xij - fsj(β) for each s → i(α)
13. Let xij = xij + fj(β)t for each i(α) → t
14. (f) Update capacities for next graph to be executed according to new assignment X
15. Output X (denoted by X∗ )

Analysis. To prove that ALG-PS indeed computes a Paretostable assignment, we need to show two things-first, that the assignment X ∗ returned by the algorithm is stable; this follows easily from stability of the original assignment and that reassigning according to augmenting paths and cycles preserves stability.

Second, we need to show that X ∗ is Pareto efficient, i.e., no further Pareto improvements are possible when the algorithm terminates. The difficulty here is that the assignment X changes through the course of the algorithm, and therefore we need to show that, for instance, no other augmenting paths can be found after the network H has been executed, even though the assignment X that was used to define the network H(X) has been changed (and similarly for all augmenting cycles). That is, while we compute maximum flows in H(X) to find all augmenting paths for a given assignment X, we need to show that no new augmenting paths have showed up in any updated assignments computed by the algorithm. Similarly, finding (i, α) augmenting cycles via Hi,α(X) for some assignment X does not automatically imply that no further (i, α) augmenting cycles will ever be found in any of the (different) assignments computed through the course of the algorithm, since the assignments of all nodes can change each time when a maximum flow is computed, leading to the possibility of new valid s-t paths, and therefore possibly new augmenting cycles. That this does not is due to a careful choice of the construction of the networks H, Hi,α, Hj,β; in fact, it is possible to construct examples showing that this does not hold for other, perhaps more natural, definitions of the networks.

Our main claim is stated next. The proof uses the assignment-independence of the structure of the networks H,Hi,α,Hj,β to argue that if there is an augmenting path in any assignment produced after H is executed, we could not have found the maximum flow in H(X) to begin with, a contradiction; the argument for augmenting cycles uses a similar idea. All proofs can be found in the full version of the paper 2 .

Proposition 4.6. There is no augmenting path after graph H is executed, and no augmenting cycle associated with i (resp. j) at level α (resp. β) after graph Hi,α (resp. Hj,β) is executed in ALG-PS.

The above claim, together with Lemma 4.3, implies that the outcome returned by ALG-PS is indeed a Pareto-efficient assignment as required.

Running time. Each graph H,Hi,α and Hj,β can be constructed in time O(m2n2 ), where n = |A| and m = |B|, and there are O(mn) such graphs in all. Each graph has O(mn) vertices, and is executed exactly once in time O(m3n3 ), which is the running time for maximum flow using any classic network flow algorithm. Therefore, the running time of the algorithm is in O(m4n4 ). We summarize this below.

Theorem 4.7. Algorithm ALG-PS computes a Pareto-stable assignment in strongly polynomial time O(m4n4 ).

We note that the number of borrower categories in Zopa is a small constant, so this algorithm computes a Paretostable assignment in our reduced marketplace (A, C) in time O(n4 ) where n = |A| is the number of lenders. In fact, a sharper bound on the running time of the algorithm is O((∑k∈M |Pk|)4 ), where |Pk| is the length of k's preference list. This means that even when each category contains a single borrower as in Prosper (so m is large), the runtime remains practically feasible: since lenders usually place bids on only a small number of borrowers in typical social lending markets, ∑k∈M |Pk| = O(n) leading to runtime O(n4 ).

Computing the Market Clearing Assignment. Having computed allocations X ∗ = (x∗iCr ) between lenders and borrower categories using algorithm ALG-PS, we now need to allocate the amount x∗iCr amongst borrowers in Cr. Note that by feasibility of X ∗ for (A, C), we have ∑i∈A x∗iCr ≤ ∑j∈Cr cj. We simply divide x∗iCr amongst borrowers in Cr proportional to their demands:

2 http://www.ntu.edu.sg/home/ningc/paper/ijcai11-z.pdf

This allocation is feasible since ∑j∈Cr yij = x∗iCr and ∑i∈A yij ≤ cj. This assignment Y = (yij) can be proven to satisfy all the properties claimed in Theorem 3.2 for the actual marketplace M = (A, B), and is our desired output.

Acknowledgements. We are very grateful to Gabrielle Demange, Bettina Klaus, Fuhito Kojima, Mohammad Mahdian, Preston McAfee, David Pennock, Michael Schwarz and anonymous referees for helpful discussions and comments.