# an_algorithmic_introduction_to_savings_circles__50b20c27.pdf

An Algorithmic Introduction to Savings Circles

Rediet Abebe1, Adam Eck2, Christian Ikeokwu1, Samuel Taggart2

1 University of California, Berkeley 2 Oberlin College

Rotating savings and credit associations (roscas) are informal ﬁnancial organizations common in settings where communities have reduced access to formal ﬁnancial institutions. In a rosca, a ﬁxed group of participants regularly contribute sums of money to a pot. This pot is then allocated periodically using lottery, aftermarket, or auction mechanisms. Roscas are empirically well-studied in economics. They are, however, challenging to study theoretically due to their dynamic nature. Typical economic analyses of roscas stop at coarse ordinal welfare comparisons to other credit allocation mechanisms, leaving much of roscas ubiquity unexplained. In this work, we take an algorithmic perspective on the study of roscas. Building on techniques from the price of anarchy literature, we present worst-case welfare approximation guarantees. We further experimentally compare the welfare of outcomes as key features of the environment vary. These cardinal welfare analyses further rationalize the prevalence of roscas. We conclude by discussing several other promising avenues.

1 Introduction Rotating saving and credit associations (roscas) are ﬁnancial institutions common in lowand middle-income nations, as well as immigrant and refugee populations around the world. In a rosca, a group of individuals meet regularly for a deﬁned period of time. At each meeting, members contribute a sum of money into a pot, which is then allocated via some mechanism, such as a lottery or an auction. Recipients often use this money to purchase durable goods (e.g., farming equipment, appliances, and vehicles), to buffer shocks (e.g. an unexpected medical expense), or to pay off loans. Roscas often exist outside of legal frameworks and do not typically have a central authority to resolve disputes or enforce compliance. Instead, they provide a decentralized mechanism for peerto-peer lending, where members who receive the pot earlier borrow from those who receive it later. They also create a structure for mutual support and community empowerment. Roscas are used in over 85 countries and are especially prevalent in contexts where communities have reduced access to formal ﬁnancial institutions (Aredo 2004; Bouman 1995a; Klonner 2002; La Ferrara 2002; Raccanello and Anand 2009). Roscas account for about one-half of

Copyright 2022, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

Cameroon s national savings. Likewise, over one in six households in Ethiopia s highlands participate in ekub, the region s variant of roscas Bouman (1995a). Due to their ability to provide quick, targeted support within communities, roscas and other mutual aid organizations often play an instrumental role when communities experience shocks and disasters (Chev ee 2021; Mesch et al. 2020; Travlou 2020). Roscas are well-studied in the economics literature, with economic theory on the subject pioneered by Besley, Coate, and Loury (1993); Kovsted and Lyk-Jensen (1999); Kuo (1993) (see supplement for further related works). This line of work seeks to explain how roscas act as insurance, savings, and lending among members. While such studies have deepened our understanding of roscas, they are typically constrained in two main ways. First, the standard economic approach solves exactly for equilibria, which can be especially difﬁcult due to the dynamic nature of roscas. Second, much of the existing theory focuses on coarse-grained comparisons between the welfare of roscas and other mechanisms for allocating credit. In part due to these coarse comparisons, this work often concludes that roscas allocate credit suboptimally, leaving open the question of why roscas are prevalent in practice. In this work, we initiate an algorithmic study of roscas. Viewing roscas through the lens of approximation and using techniques from the price of anarchy literature, we study the welfare properties of rosca outcomes without directly solving for them. We speciﬁcally quantify the allocative efﬁcacy of roscas: how well do roscas coordinate saving and lending among participants with heterogeneous investment opportunities? We show roscas enable a group s lending and borrowing in a way that approximately maximizes the groups total utility. We do so under a wide range of assumptions on both participants values for investment and the mechanisms used for allocating the pots. This robustness may provide one explanation for their prevalence. Our work builds on the saving and lending formulation of Besley, Coate, and Loury (1994). We assume each participant seeks to purchase an investment, such as a durable good, but can only do so upon winning the rosca s pot. We analyze the welfare properties of typical pot allocation mechanisms, such as swap roscas, where the participants are given an initial (e.g. random) allocation and then swap positions in an after-market through bilateral trade agree-

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

ments. We also study the price of anarchy in auction-based roscas where, during each meeting, participants bid to decide a winner among those who have not yet received a pot. During each round, participants must weigh the value of investing earlier against the utility loss from spending to win that round. Our technical contributions are as follows: For swap roscas, we prove that all outcomes guarantee at most a factor 2 loss. For auction-based roscas, we give full-information price of anarchy results: we study second-price sequential roscas and give a price of anarchy of 3 under a standard nooverbidding assumption. For ﬁrst-price sequential roscas, we provide a ratio of (2e + 1)e/(e 1). Our work provides new applications of and extensions to the smoothness framework of Syrgkanis and Tardos (2013). However, due to the round-robin (i.e you can only win once) property of rosca allocations and the fact that all payments are redistributed to members, standard smoothness arguments do not immediately yield bounds in our setting. Via a new sequential composition argument, we show that roscas based on smooth mechanisms are themselves smooth, and we go beyond smoothness to bound the distortionary impact of redistributed payments on welfare. Our above results hold under the well-studied assumption of quasilinear utility for money. We extend most of our theoretical results to nonlinear utility functions, and also use simulations to consider the impact of nonlinear utilities in several natural families of swap roscas. Overall, this work aims to provide greater exposure for mutual aid organizations more generally and roscas to the algorithms community. In doing so, we present a case study showing how algorithmic game theory can provide a useful perspective for further understanding fundamental questions related to these ﬁnancial organizations. Given their prevalence and efﬁcacy, insights into roscas can help inform the design of other safety net programs, especially for communities that already commonly use roscas. As new technologies are introduced in low-access contexts, also, the need to understand existing, prevalent ﬁnancial organizations is even more pressing. We close the paper with discussion of promising research directions.

2 Model and Preliminaries A rosca consists of n participants and takes place over n discrete and ﬁxed time periods, or rounds. During each round three things occur: (1) each participant contributes an amount p0 into the rosca common pot, (2) a winner for the pot is decided among those who have not yet won, and (3) the winning participant is allocated the entire pot worth np0. Typically, the contributions p0 are decided ex ante during the formation of the rosca. As is common in previous literature, we will not model the selection process for p0, but instead take it as given (c.f. Klonner 2001). With the rosca contribution p0 ﬁxed, we can cast roscas as an abstract multi-round allocation problem, where every participant is allocated exactly one pot, and each pot is allocated to exactly one participant, illustrated in Alg 1. Each participant s value for the allocations is described by a realvalued vector vi = (v1 i , . . . , vn i ), with vt i representing participant i s value for winning the pot in round t and having

access to that money at that time. We denote allocations by x = (x1, . . . , xn), where xi = (x1 i , . . . , xn i ) is an indicator vector, and xt i = 1 if and only if participant i receives the pot in round t. Based on a common observation from previous literature, we can further assume that values for allocation are non-increasing over time: i.e., for t < t and any i, vt i vt i . This follows if rosca funds are used to make lumpy investments, e.g., in a durable good, as is common in practice (Besley, Coate, and Loury 1993, 1994; Kovsted and Lyk-Jensen 1999; Klonner 2008). Participants prefer to own the good earlier rather than later, though different participants values for owning the good earlier may vary.

Algorithm 1: Rosca Multi-Round Allocation Constants: n: the number of participants and rounds in the rosca. p0: amount contributed by each participant to the pot in each round of the rosca. Inputs: Valuations v, where vt i indicates the value to participant i of winning the pot in round t. Alloc an allocation mechanism.

For each round t {1, 2, . . . , n}

1. Each participant contributes p0 into the pot 2. Alloc selects the winning participant (who has not yet won a round) 3. The winning participant receives the pot worth np0 4. Optional: Some participants make payments based on Alloc, which are redistributed to the others as rebates.

2.1 Roscas with Payments A variety of different pot allocation mechanisms are common in practice (see Ardener 1964; Bouman 1995b). This work considers roscas where participants make payments to inﬂuence their allocations, and assumes as a ﬁrst-order approximation that participants are rational. Payments in roscas take the form p = (p1, . . . , pn), where pi = (p1 i . . . , pn i ). As participants abilities to save money over time are typically limited, we assume participants utilities are additively separable across rounds, but possibly nonlinear in money. That is, participant i with value vector vi has utility for allocation xi and payments pi given by

uvi i (xi, pi) = xi vi X

for some disutility function C that is both increasing and satisﬁes C(0) = 0. In a given round, pt i could be positive, if the allocation mechanism requires i to make payments, or negative, if a different participant s payments are redistributed to i. We refer to the latter as rebates, and assume all payments are redistributed each round, i.e., P i pt i = 0 for all t. A participant who makes positive payments in round t has less money to spend in round t, and one who receives rebates in the form of negative payments has more to spend. The function C( ) describes participants preferences for these changes in wealth. A more precise interpretation of C(pt i) is as follows: assume that each participant i has a per-round income of w. Without participating in the rosca, they would receive a utility U(w) from consumption of that income, for

some increasing consumption utility function U. Upon contributing p0 into the rosca pot each round, the participant s baseline consumption utility is U(w p0). If the rosca s allocation procedure requires additional payments (or distributes rebates) of pt i, a participant s utility from consumption becomes U(w p0 pt i). The disutility function C then represents the participant s difference in utility for consumption, C(p) = U(w p0) U(w p0 p),

which is increasing. A large body of anthropological and empirical work on roscas shows that participants in the same rosca tend to have similar economic circumstances (see Ardener 1964; Aredo 2004; Mequanent 1996). So, following the theory literature, we assume U and w (and hence C) are identical across participants, even if the value for receiving the pot differ between participants (Besley, Coate, and Loury 1994; Kovsted and Lyk-Jensen 1999; Klonner 2001). It is typical to assume consumption utility U is weakly concave, and hence C is weakly convex (Anderson and Baland 2002; Klonner 2003b, 2001). The special case of quasilinear utilities, where C(p) = p, is especially well-studied in the algorithmic game theory literature. To measure allocative performance of a rosca, we study the participants total utility:

WELv(x, p) = X

i uvi i (xi, pi).

Following the interpretation of C in terms of consumption utility U, WELv(x, p) represents the gain in utility to all participants for a given allocation x and payments p, above the baseline total utility of n2U(w p0), obtained by each of the n participants obtaining utility U(w p0) for n rounds. Among all possible matchings x and payment proﬁles p Rn n, the optimal welfare-outcome is given by the maximum-weight matching x = argmaxx P i xi vi and payments p = (0, . . . , 0), whose welfare is denoted OPT(v) = WELv(x , p ). To quantify the inefﬁciency of a rosca outcome (x, p), we study the approximation ratio OPT(v)/WELv(x, p). When rosca outcomes are equilibria of auctions, as in Section 3, this ratio is also known as the price of anarchy (Po A).

Roadmap. The remainder of this paper proceeds as follows: In Section 3, we prove a constant-approximation for auction roscas. We do the same for swap roscas in Section 4. Both sets of results focus on quasilinear utilities, where C(p) = p, and hence all welfare loss comes from allocative inefﬁciency. We extend these results to nonlinear utilities in the supplement. In Section 4, we further conduct experiments to study the impact of nonlinear utility on swap rosca welfare. We give directions for future work in Section 5.

3 Auction Roscas Auctions are a common mechanism for allocating pots in roscas (Ardener 1964; Bouman 1995a; Klonner 2003a). Two major sources of variety in auction roscas are (1) when bids are solicited from participants and (2) the type of auction run for the bidding process. The bidding may occur either at the

beginning, in which case a single (up-front) auction determines the full schedule of pot allocations, or sequentially, in which case a separate auction is held each period to determine the allocation for the corresponding pot. We consider sequential ﬁrstand second-price (equivalently, ascendingand descending-price) auctions, as well as up-front all-paystyle auctions. Payments are typically redistributed as rebates among all of the non-winning participants. The fact that outcomes depend on participants bidding behavior complicates our analysis. We assume participants play a Nash equilibrium (NE) of the rosca s auction game. That is, their bidding strategy maximizes their utility given the bidding strategies of other participants. Our analysis will use the smoothness framework of Syrgkanis and Tardos (2013), along with new arguments to handle rosca-speciﬁc obstacles. We assume participants have quasilinear utilities.

3.1 Proof Template: Up-Front Roscas We begin our analysis by considering roscas with up-front bidding. In an up-front rosca, each participant i submits a bid bi at the beginning of the rosca. Participants pay their bids, and are then assigned pots in decreasing order of their bids, with the highest participant receiving the pot in round 1, and so on. Each participant i s payments are redistributed evenly among the other participants in the form of reduced per-period payments into the rosca. Under quasilinear utilities, it is not relevant to the participants utilities what round payments are made; the only relevant outcome is total payments, which we write as pi = P t pt i when context allows. We can further assume per-period payments remain ﬁxed and that the participants receive the redistributed payments up-front in the form of a rebate. We decompose the participants total payments into their gross payments ˆpi and rebates ˆri, with pi = ˆpi ˆri. Formally:

Deﬁnition 1. In an up-front rosca with quasilinear participants, each participant i submits a bid bi, with b = (b1, . . . , bn). Let ri denote the rank of participant i s bid. Allocations are xt i(b) = 1 if t = ri and 0 otherwise. Participant i s gross payment is ˆpi(b) = bi, and their rebate is ˆri(b) = P i =i bi /(n 1).

Our auction rosca analyses all follow from a two-step argument. First, we use or modify the smoothness framework of Syrgkanis and Tardos (2013) to obtain a tradeoff between participants utilities and their gross payments. Without rebates, typical auction analyses conclude by noting that high payments imply high welfare. However, because gross payments in roscas are redistributed, it could happen that both gross payments and rebates are high, but welfare is low. Our second step is to rule out this problem. For up-front roscas, we can demonstrate both steps simply. The ﬁrst step follows from Lemma A.20 of Syrgkanis and Tardos (2013):

Lemma 1. With quasilinear participants, any Nash equilibrium b of any up-front rosca with values v satisﬁes X

i uvi i (b) 1

i ˆpi(b). (1)

The left hand side of (1) is the equilibrium welfare. It

therefore sufﬁces for the second step to upper bound the gross payments on the right hand side.

Lemma 2. Let b be a Nash equilibrium of an up-front rosca with quasilinear participants and values v. Then, for any participant i, ˆpi(b) vi xi(b).

Proof. Assume for some i that ˆpi(b) > vi xi(b). Then participant i must be overbidding. They could improve their utility by bidding 0, which, in an up-front rosca, does not change their rebates: ˆri(0, b i) = ˆri(b) > vi xi(b) ˆpi(b) + ˆri(b).

Since P i vi xi(b) is equal to the equilibrium welfare, Lemmas 1 and 2 together imply the following.

Theorem 1. With quasilinear participants, every Nash equilibrium of an up-front rosca has Po A at most 4.

3.2 Sequential Roscas We now consider roscas with separate sequentially-held ﬁrstor second-price auctions for each pot as opposed to the single-auction format from the previous section.

Deﬁnition 2. A ﬁrst-price rosca runs a ﬁrst-price auction in each round. That is, if the highest-bidding participant in round t among those who have not yet won is participant i , with bid bt i , then xt i = 1, xt i = 0 for all other participants i. The gross payments are ˆpt i = bt i and ˆpt i = 0 otherwise. The rebates are ˆrt i = bt i /(n 1) for all i = i .

Deﬁnition 3. A second-price rosca runs a second-price auction in each round. That is, if the highest-bidding participant in round t among those who have not yet won is i , with second-highest bid bt (2), then xt i = 1, xt i = 0 for all other participants i. Gross payments are ˆpt i = bt (2) and ˆpt i = 0 otherwise. Rebates are ˆrt i = bt (2)/(n 1) for all i = i .

Sequential auctions require a monitoring scheme in which the auctioneer discloses information about participants bids after each round. Our results will hold for any deterministic monitoring scheme. A key subtlety is that participants actions are now behavioral strategies: that is, at each stage, participants observe the disclosed history of play so far and can condition their future bids on this history. We denote the vector of behavioral strategies by a = (a1, . . . , an), and denote by bt i participant i s bid in a round t. As with up-front roscas, we ﬁrst derive a tradeoff between utility and gross payments, and second consider the impact of rebates. The sequential format complicates both steps. Our ﬁrst step will follow from a novel composition argument, where we show that both ﬁrstand second-price roscas inherit a tradeoff from their single-item analogs. For second-price roscas, a standard no-overbidding assumption then bounds the auction s rebates and implies a welfare bound. For ﬁrst-price roscas, we give a more involved analysis that bounds overbidding and yields an unconditional guarantee. Overbidding can both occur in equilibrium and harm welfare, so such an analysis is necessary. Observe that, ﬁrstand second-price roscas can be thought of as the sequential composition n single-item auctions, with a rule excluding past winners. Formally:

Deﬁnition 4 (Round-Robin Composition). Given singleitem auction M, the n-item round-robin composition of M is a multi-round allocation mechanism for n items using the following procedure: Each round t, each participant i who has not yet been allocated an item submits a bid bt i. The mechanism then runs M among the remaining participants to determine the allocation and payments for that round. The following deﬁnition of smoothness, adapted from Syrgkanis and Tardos (2013), lets us characterize both ﬁrstand second-price roscas with the same framework. For our purposes, it applies to any auction where in round t, each bidder who has not yet won submits a real-valued bid bt i, which we term sequential single-bid auctions. Note that this includes single-item auctions. We will show that smoothness of single-item auctions implies smoothness of their roundrobin composition. Deﬁnition 5. Let M be a sequential single-bid auction. We say M is (λ, µ1, µ2)-smooth if for every value proﬁle v and action proﬁle a, there exists a randomized action a i (ai, v) for each i such that: X

i(vi xi(a i (ai, v), a i) pi(a i (ai, v), a i)

λOPT(v) µ1 X

i ˆpi(a) µ2 X

where Bi(a) is i s bid in the round where they win, or 0 if no such round exists. Syrgkanis and Tardos (2013) show that single-item ﬁrstprice and second-price auctions are (1 1/e, 1, 0)-smooth, and (1, 0, 1)-smooth, respectively. However, the smoothness result they prove for a form of sequential composition fails to hold for round-robin composition, due to the cardinality constraint on allocations as in our setting. Here, we instead give a new composition argument tailored speciﬁcally to the rosca setting, that relies on values decreasing in time. Our composition result follows the following useful deﬁnition: Deﬁnition 6. A single-item mechanism M with allocation rule x and payments p is strongly individually rational (IR) if (1) for every proﬁle of actions a, xi(a) = 0 only if ˆpi(a) = 0, and (2) there exists an action such that for all i and a i, ˆpi( , a i) = 0.

Lemma 3. Let M be a strongly individually-rational singleitem mechanism. If M is (λ, µ1, µ2)-smooth for λ 1 and µ1, µ2 0, then its round-robin composition is (λ, µ1 + 1, µ2)-smooth as long as vt i vt+1 i for all i and t. Our proof of this lemma, presented in the supplement, augments the main idea from the Syrgkanis and Tardos (2013) composition result with ideas from Kesselheim, Kleinberg, and Tardos (2015), who consider smoothness of non-sequential mechanisms for cardinality-constrained allocation environments. As a corollary of Lemma 3, we obtain that ﬁrstand second-price roscas are respectively (1 1/e, 2, 0) and (1, 1, 1)-smooth. We next analyze the impact of rebates. If no participant overbids, then payments (and hence rebates) are necessarily bounded by values, and we obtain a similar conclusion to Lemma 2. Moreover, we show in the supplement that

a no-overbidding assumption is necessary for second-price roscas, as is often the case for auctions with second-price payments. The assumption we require is as follows: Deﬁnition 7. Action proﬁle a satisﬁes no-overbidding if Bi(a) vi xi(a) for every participant i. Theorem 2. Let M be a strongly IR, single-item auction that is (λ, µ1, µ2)-smooth, with λ 1. With quasilinear participants, every no-overbidding Nash equilibrium of the corresponding auction rosca with rebates has Po A at most (2 + µ1 + µ2)/λ.

Proof. Lemma 3 implies that the rosca is (λ, 1 + µ1, µ2)- smooth before rebates. We can therefore write: X

i uvi i (a) X

i uvi i (a i , a i)

i(vi xi(a i , a i) ˆpi(a i , a i))

λOPT(v) (1 + µ1) X

λOPT(v) (1 + µ1 + µ2) X

λOPT(v) (1 + µ1 + µ2) X

Since both P i uvi i (a) and P i vi xi(a) are equal to equilibrium welfare, the result follows.

Corollary 1. For quasilinear participants, any Nash equilibrium of the ﬁrst-price rosca satisfying no-overbidding has Po A at most 3e/(e 1). Corollary 2. For quasilinear participants, any Nash equilibrium of the second-price rosca satisfying no-overbidding has Po A at most 3.

3.3 Relaxing No-Overbidding The no-overbidding assumption in the previous section rules out behavior where participants overbid in early rounds to induce others to bid high in later rounds, thereby resulting in high rebates. When this behavior is extreme, participants payments could conceivably far exceed their values, which in turn complicates the smoothness-based approach. The following example gives a Nash equilibrium of a ﬁrst-price rosca where overbidding leads to welfare loss. Example 1. Consider three participants, with v1 = (1, 0, 0), v2 = (2, 2, 0), and v3 = (2, 2, 0). The following behavioral strategies form a Nash equilibrium. Participant 1 bids 2 in round 1. Participants 2 and 3 bid 1 in round 1. If participant 1 bids less than 2 in round 1, participants 2 and 3 bid 0 in round 2. Otherwise, they bid 2. The optimal welfare is then 4, but the equilibrium welfare is 3.1

Despite the loss exhibited in Example 1, we can obtain a constant price of anarchy for ﬁrst-price roscas without an overbidding assumption. Lemma 4 below shows that overbidding cannot drive payments much higher than equilibrium welfare. The lemma extends the following logic: In

1This example does not satisfy the reﬁnement of subgame perfection, though our welfare guarantees do not need this restriction.

equilibrium, the participant who wins in the ﬁnal round has no competition, and is therefore making zero payments. Consequently, the participant who wins in the second-to-last round cannot expect any rebates from round n, and therefore has no incentive to overbid. This, in turn, limits the rebates due the participant who wins the round before that, and so on. These limits on rebates limit the extent of overbidding that might occur. Throughout this section, we index participants such that in round t, the winner is participant t. Lemma 4. Fix a Nash equilibrium of a ﬁrst-price rosca. Then:

ˆpt t vt t + 1 n 1

t =t+1 vt t ( n n 1)t t 1.

We provide the proof in the supplementary materials. Theorem 3. In any Nash equilibrium of the ﬁrst-price rosca, the Po A is at most (2e + 1)e/(e 1). The result follows from summing the bounds on ˆpi(a) from Lemma 4, which can be arranged to obtain an upper bound of e P i vi xi(a) of the total gross payments. The theorem then follows from applying smoothness as before.

3.4 Extension to Nonlinear Utilities In the supplement, we extend the price of anarchy results above beyond quasilinear utilities. With arbitrary convex cost for payments C, the setting comes to resemble hard budgets, for which the price of anarchy is known to be poor. We parametrize our results by upper (β) and lower (α) bounds on the slope C . We give performance guarantees which scale linearly with the ratio β/α. For up-front roscas, our bounds are unconditional, while for sequential roscas, we assume an analogous no-overbidding condition to the quasilinear version.

4 Swap Roscas Several common rosca formats eschew competition between participants in allocating pots. Examples include roscas based on random lottery allocations or those based on seniority or social status (Anderson, Baland, and Moene 2009; Kovsted and Lyk-Jensen 1999). To improve total welfare, it is common practice for participants to engage in an aftermarket by buying or selling their assigned allocations when it is mutually beneﬁcial, i.e., by swapping rounds in the rosca (Mequanent 1996). In this section, we formally deﬁne these swap roscas and show that, for participants with quasilinear utilities (C(p) = p), this aftermarket is guaranteed to converge to an outcome that yields at least half of the optimal welfare. We then present experimental results showing that this guarantee is often better, even for strictly convex C.

4.1 Theoretical Analysis As is common in the literature and in practice, we assume that the aftermarket occurs via a series of two-agent swaps (Mequanent 1996; Bouman 1995b; Ardener 1964). We assume these swaps can occur at any round t. We denote by pt the vector of payments for round t, which are initialized to 0

for each round and updated as swaps occur. A swap occurs if and only if it is utility-improving for two participants under some set of payments. Formally: Deﬁnition 8. Given initial allocation x and payments pt at round t, a swap is given by a pair of participants i, i assigned to rounds j, j t, respectively, and a payment ˆp. A swap is valid if vj

i C(pt i + ˆp) > vj i C(pt i) and vj i C(pt i ˆp) > vj

i C(pt i ). Upon executing a swap, set xj i, xj

i , xj i 1, pt i pt i + ˆp, and pt i pt i ˆp. Note that with quasilinear participants, all valid swaps must strictly improve allocative efﬁciency since C(p) = p. That is, vj

i + vj i > vj i + vj

i , and the validity of a swap does not depend on the initial payments pt. We then study roscas of the following form: Deﬁnition 9. A swap rosca starts from an initial allocation x and initial payments p = {pt}n t=1 of 0 for each participant and round. At each round t = 1, . . . , n, participants execute valid swaps and we update the allocation and payment accordingly. We do so until there are no valid swaps. Note that for non-linear C, new swaps may become valid moving from round t to t+1, as each new round s payments reset to 0. For quasilinear participants, however, Deﬁnition 9 executes all swaps in round 1. In this case, the resulting allocation is guaranteed to be stable to pairwise swaps. Deﬁnition 10. An allocation x is swap-stable if for all participants i, i assigned to j, j , we have that vj i + vj

i + vj i . For quasilinear participants, swap-stability is guaranteed regardless of the initial allocation. Convergence of the swap process follows from the fact that the total allocated value P i vi xi strictly increases each swap and that the number of allocations is ﬁnite. Theorem 4. For quasilinear participants, the welfare approximation for every swap rosca is at most 2.

Proof. Without loss of generality, assume that the welfareoptimal allocation assigns each participant i to be allocated the pot in round i, so the optimal welfare is P i vi i. Now let π(i) denote the round when participant i is allocated the pot in the swap rosca s ﬁnal allocation, and π 1(i) the participant allocated the pot in round i. Note that π and π 1 are bijections. Furthermore, under quasilinear utilities, all payments between participants are welfare-neutral, and hence the rosca welfare is given by P i vπ(i) i . For any participant i, note that swap-stability implies

vπ(i) i + vi π 1(i) vi i + vπ(i) π 1(i) vi i.

Summing over all participants i, we get X

i vπ(i) i + X

i vi π 1(i) X

Since π and π 1 are bijections, both sums on the lefthand side are equal to the rosca welfare, and the righthand side is the optimal welfare, giving us a 2-approximation.

Example 1 in the appendix shows that this bound is tight.

4.2 Experimental Results

The results presented so far partially rationalize the prevalence of auction and swap roscas. However, two limitations prevent a comprehensive view of roscas allocative efﬁciency. First, the worst-case nature of our theoretical results give little detail about outcomes in typical instances. Second, our results hold only under quasilinear utilities, which may be less realistic for extremely vulnerable participants. This section complements our theoretical results with computational experiments that shed light on these latter questions for swap roscas. We simulate swap roscas under natural instantiations of participants values, and with participants costs for payments taking a well-studied but nonlinear form. We ﬁnd that the approximation ratio of these roscas in more typical scenarios is signiﬁcantly better than the worst-case ratio, even after relaxing quasilinearity. Our experiments also allow us to study the way rosca performance changes as participants values for their payments become more convex. In particular, we use constant relative risk aversion (CRRA) utilities, given by

C(p; W, a) = (1 a) 1(W 1 a (W p)1 a),

where the parameter W represents the participant s starting wealth, and a governs the convexity of the function, with a = 0 being quasilinear. For a > 0, CRRA utilities have a vertical asymptote at p = W, as participants are unable to spend beyond their means. We choose W to be less than many of our participants maximum values for the rosca pot. This is intended to capture that most participants cannot afford the durable good without the rosca (Anderson and Baland 2002). Note that as a 1, C(p; W, a) ln(W) ln(W p). We choose CRRA utilities because they are standard for modeling preferences for wealth in economics (see, e.g. Romer 1996). We give two sets of experimental results. In each, we run 9and 30-person roscas (typical sizes for smalland medium-sized roscas), and compare three quantities: the optimal welfare under our selected value proﬁle, the expected approximation ratio of a random allocation before any swaps, and the approximation ratio for a swap rosca run from a random allocation. Our swap roscas are simulated according to the description in Section 4. For a pair of participants i and j for whom there exists a valid swap, there are generally many payments which will incentivize a swap and we choose the smallest such payment.

4.3 Experiment: CRRA Utilites

Our ﬁrst experiment ﬁxes a proﬁle of participant values and studies the performance of swap roscas as the convexity parameter a and starting wealth W vary. The value proﬁle, comprised of 9 participants, features 6 with cutoff values of the form vt i = v for all i ˆt for some ˆt, and three participants with values which are roughly linearly decreasing in time. The average maximum value among cutoff participants is 5, which matched the average value for linearly decreasing values. We give all value proﬁles explicitly in the supplement. We consider values of a ranging from 0 (quasilinear) to 2 (very convex), focusing on smaller values, as

larger values of a tend to represent very similar, extreme functions. We take W in the range {1, . . . , 5}, as this puts participants wealth levels generally below their values for the rosca pot. Welfare values are averaged over 10, 000 simulation runs, each starting with a random initial allocation that participants can pay to improve through swaps. Results for this simulation can be found in Table 1.

W 1 2 3 4 5

0 1.035 1.034 1.035 1.034 1.035 0.1 1.121 1.119 1.070 1.067 1.063 0.2 1.122 1.121 1.080 1.074 1.074 0.3 1.122 1.119 1.118 1.086 1.081 0.5 1.122 1.124 1.121 1.119 1.120 0.75 1.122 1.122 1.123 1.121 1.121 1 1.124 1.122 1.121 1.123 1.122 1.5 1.123 1.123 1.122 1.122 1.123 2 1.122 1.125 1.123 1.122 1.123

Table 1: Swap Rosca Performance Under Different CRRA Parameters (OPT = 45, random baseline ratio = 1.601)

Across all values of W, the approximation ratio of swap roscas generally worsens (increases) as the level of convexity a increases. Intuitively, this is likely due to the fact that since C is convex, a participant receiving payments for a swap values them less than the participant offering the payments. Consequently, swaps are less likely to occur, even if they would lead to improved allocative efﬁciency. Meanwhile, the effect of W depends on the level of convexity a. When 0 < a < 0.5, participants with higher wealth W have more money to spend on swaps, making swaps more likely to occur and hence improve allocative efﬁciency. Thus, approximation ratios improve (decrease) with higher W. However, as convexity increases, the disincentive to swap caused by convexity overcomes the beneﬁt of having greater wealth with which to pay for swaps, and the approximation ratios no longer change with W. For all parameter values chosen, however, swap roscas led to a marked improvement over the approximation ratio from random allocation alone, suggesting that even under extreme convexity, participants are able to identify local improvements to social welfare. We also repeat this experiment with a 30-participant rosca using similar value proﬁles and observe the same trends. We present the results in the supplement.

4.4 Experiment: Distributional Diversity Our second set of experiments, discussed in more detail in the supplement, varies the distribution of values across the population of participants, again for 9and 30-person roscas. This allows us to study the way the distribution of need across a population impacts rosca welfare. We ﬁnd that performance is insensitive to wide inequality in values of participants in the population.

5 Discussion and Conclusion Roscas are complex and varied social institutions, signiﬁcant for their integral role in allocating ﬁnancial resources world-

wide. In this work, we focus speciﬁcally on the allocative efﬁcacy of roscas as lending and saving mechanisms. We derive welfare guarantees for roscas under a variety of allocation protocols and show that many commonly-observed roscas provide a constant factor welfare approximation to the optimal allocation. This guarantee, we believe, gives partial explanation for the ubiquity of roscas. In addition to these speciﬁc results, our work also serves as proof of concept for the potential for techniques from algorithmic game theory to help us better understand roscas and, more generally, how communities self-organize to create opportunity. We highlight ideas for further exploration below. First, our work modeled the savings aspect of roscas, though roscas are also used as insurance when participants experiencing unanticipated needs may bid to obtain the pot earlier than they may have otherwise planned (Calomiris and Rajaraman 1998; Klonner 2003b, 2001). There remain many gaps in our understanding of roscas when participants values and incomes evolve stochastically over time. Another challenge is understanding the tension between allocative efﬁciency and wealth inequality. Participants with valuable investment opportunities might not bid as aggressively if their low wealth causes them to value cash highly. This is exacerbated when participants experience income shocks, which are often experienced by economically vulnerable individuals (Abebe, Kleinberg, and Weinberg 2020; Nokhiz et al. 2021). Ethnographic work shows that altruism plays a signiﬁcant role in alleviating this tension (Klonner 2008; Sedai, Vasudevan, and Pena 2021). Roscas often serve a dual role of community-building institutions. Consequently, participants tend to observe signals about each others shocks, and act with mutual aid in mind (Klonner 2008; Mequanent 1996). Though roscas often work outside formal institutions, studies show that rosca enforcement is not often an issue. For instance, (Smets 2000; Van den Brink and Chavas 1997) show that early recipients of the pot rarely default, in part due to strong community norms and standards. These considerations often go unaccounted for in theoretical studies of roscas. A deeper understanding of community norms and standards can shed more light on rosca enforcement mechanisms and robustness. Finally, there are many questions on how aspects of the population and environment govern the performance of roscas: i.e., under what conditions would one prefer one type of rosca over another? Similarly, how do roscas perform when their members evolve over time, e.g., with some participants joining part way through the rosca and potentially holding more leverage? Likewise, rosca formation is known to be crucial, with many roscas preferring individuals with similar socio-economic backgrounds. Modeling and examining the rosca formation process can improve our understanding of the interaction between the rosca formation process and their functionality, efﬁcacy, and robustness.

References Abebe, R.; Kleinberg, J. M.; and Weinberg, S. M. 2020. Subsidy Allocations in the Presence of Income Shocks. In AAAI, 7032 7039.

Anderson, S.; and Baland, J.-M. 2002. The economics of roscas and intrahousehold resource allocation. The Quarterly Journal of Economics, 117(3): 963 995. Anderson, S.; Baland, J.-M.; and Moene, K. O. 2009. Enforcement in informal saving groups. Journal of development Economics, 90(1): 14 23. Ardener, S. 1964. The comparative study of rotating credit associations. The Journal of the Royal Anthropological Institute of Great Britain and Ireland, 94(2): 201 229. Aredo, D. 2004. Rotating savings and credit associations: characterization with particular reference to the Ethiopian Iqqub. Savings and Development, 179 200. Besley, T.; Coate, S.; and Loury, G. 1993. The economics of rotating savings and credit associations. The American Economic Review, 792 810. Besley, T.; Coate, S.; and Loury, G. 1994. Rotating savings and credit associations, credit markets and efﬁciency. The Review of Economic Studies, 61(4): 701 719. Bouman, F. 1995a. Rosca: On the Origin of the Species/Rosca: sur L Origine du Phenom ene. Savings and Development, 117 148. Bouman, F. J. 1995b. Rotating and accumulating savings and credit associations: A development perspective. World development, 23(3): 371 384. Calomiris, C. W.; and Rajaraman, I. 1998. The role of ROSCAs: lumpy durables or event insurance? Journal of development economics, 56(1): 207 216. Chev ee, A. 2021. Mutual Aid in north London during the Covid-19 pandemic. Social Movement Studies, 1 7. Kesselheim, T.; Kleinberg, R.; and Tardos, E. 2015. Smooth online mechanisms: A game-theoretic problem in renewable energy markets. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, 203 220. Klonner, S. 2001. How Roscas perform as insurance. Klonner, S. 2002. Understanding Chit Funds: Prize Determination and the Role of Auction Formats in Rotating Savings and Credit Associations. New Haven, USA. Klonner, S. 2003a. Buying ﬁelds and marrying daughters: An empirical analysis of ROSCA auctions in a south Indian village. Available at SSRN 400220. Klonner, S. 2003b. Rotating savings and credit associations when participants are risk averse. International Economic Review, 44(3): 979 1005. Klonner, S. 2008. Private information and altruism in bidding ROSCAs. The Economic Journal, 118(528): 775 800. Kovsted, J.; and Lyk-Jensen, P. 1999. Rotating savings and credit associations: the choice between random and bidding allocation of funds. Journal of Development Economics, 60(1): 143 172. Kuo, P.-S. 1993. Loans, bidding strategies and equilibrium in the discount-bid rotating credit association. Institute of Economics, Academia Sinica. La Ferrara, E. 2002. Inequality and group participation: theory and evidence from rural Tanzania. Journal of Public Economics, 85(2): 235 273.

Mequanent, G. 1996. The Role of Informal Organizations in Resettlement Adjustment Process: A Case Study of Iqubs, Idirs, and Mahabers in the Ethiopian Community in Toronto. Refuge: Canada s Journal on Refugees, 30 40. Mesch, D.; Osili, U.; Skidmore, T.; Bergdoll, J.; Ackerman, J.; and Sager, J. 2020. COVID-19, Generosity, and Gender: How Giving Changed During the Early Months of a Global Pandemic. Nokhiz, P.; Ruwanpathirana, A. K.; Patwari, N.; and Venkatasubramanian, S. 2021. Precarity: Modeling the Long Term Effects of Compounded Decisions on Individual Instability. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, 199 208. Raccanello, K.; and Anand, J. 2009. Health expenditure ﬁnancing as incentive for participation in ROSCAs. Revista Desarrollo y Sociedad, (64): 173 206. Romer, D. 1996. Advanced macroeconomics. Mc Graw Hill advanced series in economics. New York: Mc Graw-Hill Companies. ISBN 9780070536678. Sedai, A. K.; Vasudevan, R.; and Pena, A. A. 2021. Friends and beneﬁts? Endogenous rotating savings and credit associations as alternative for women s empowerment in India. World Development, 145: 105515. Smets, P. 2000. ROSCAs as a source of housing ﬁnance for the urban poor: An analysis of self-help practices from Hyderabad, India. Community Development Journal, 35(1): 16 30. Syrgkanis, V.; and Tardos, E. 2013. Composable and efﬁcient mechanisms. In Proceedings of the forty-ﬁfth annual ACM symposium on Theory of computing, 211 220. Travlou, P. 2020. Kropotkin-19: A Mutual Aid Response to COVID-19 in Athens. Design and Culture, 1 10. Van den Brink, R.; and Chavas, J.-P. 1997. The microeconomics of an indigenous African institution: the rotating savings and credit association. Economic development and cultural change, 45(4): 745 772.