# An Algorithmic Introduction to Savings Circles

Rediet Abebe,1 Adam Eck,2 Christian Ikeokwu, 1 Samuel Taggart 2

###### Abstract

Rotating savings and credit associations (roscas) are informal financial
organizations common in settings where communities have reduced access to
formal financial institutions. In a rosca, a fixed 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 financial institutions
common in low- and middle-income nations, as well as immigrant and refugee
populations around the world. In a rosca, a group of individuals meet
regularly for a defined 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 peer-to-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 financial institutions (Aredo
2004; Bouman 1995a; Klonner 2002; La Ferrara 2002; Raccanello and Anand 2009).
Roscas account for about one-half of 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ée 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 Appendix A 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
difficult 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 specifically quantify the allocative efficacy 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 agreements.
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 no-
overbidding assumption. For first-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 financial organizations. Given their prevalence and efficacy, 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 financial 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
fixed time periods, or rounds. During each round three things occur: (1) each
participant contributes an amount $p_{0}$ 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 $np_{0}$. Typically, the
contributions $p_{0}$ are decided ex ante during the formation of the rosca.
As is common in previous literature, we will not model the selection process
for $p_{0}$, but instead take it as given (c.f. Klonner 2001).

With the rosca contribution $p_{0}$ fixed, 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 real-
valued vector ${\mathbf{v}}_{i}=(v_{i}^{1},\ldots,v_{i}^{n})$, with
$v_{i}^{t}$ 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
${\mathbf{x}}=({\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{n})$, where
${\mathbf{x}}_{i}=(x_{i}^{1},\ldots,x_{i}^{n})$ is an indicator vector, and
$x_{i}^{t}=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^{\prime}$ and any $i$, $v_{i}^{t}\geq v_{i}^{t^{\prime}}$. 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. $p_{0}$:
amount contributed by each participant to the pot in each round of the rosca.
Inputs: Valuations ${\mathbf{v}}$, where $v_{i}^{t}$ indicates the value to
participant $i$ of winning the pot in round $t$. $Alloc$ an allocation
mechanism.

For each round $t\in\\{1,2,\ldots,n\\}$

  1. 1.

Each participant contributes $p_{0}$ into the pot

  2. 2.

$Alloc$ selects the winning participant (who has not yet won a round)

  3. 3.

The winning participant receives the pot worth $np_{0}$

  4. 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 influence their allocations, and assumes as a first-order
approximation that participants are rational. Payments in roscas take the form
${\mathbf{p}}=({\mathbf{p}}_{1},\ldots,{\mathbf{p}}_{n})$, where
${\mathbf{p}}_{i}=(p_{i}^{1}\ldots,p_{i}^{n})$. 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 ${\mathbf{v}}_{i}$ has utility for
allocation ${\mathbf{x}}_{i}$ and payments ${\mathbf{p}}_{i}$ given by

$u_{i}^{{\mathbf{v}}_{i}}({\mathbf{x}}_{i},{\mathbf{p}}_{i})={\mathbf{x}}_{i}\cdot{\mathbf{v}}_{i}-\sum\nolimits_{t}C(p_{i}^{t}),$

for some disutility function $C$ that is both increasing and satisfies
$C(0)=0$. In a given round, $p_{i}^{t}$ 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.,
$\sum_{i}p_{i}^{t}=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(\cdot)$ describes participants’ preferences
for these changes in wealth. A more precise interpretation of $C(p_{i}^{t})$
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 $p_{0}$ into the rosca pot each round, the
participant’s baseline consumption utility is $U(w-p_{0}).$ If the rosca’s
allocation procedure requires additional payments (or distributes rebates) of
$p_{i}^{t}$, a participant’s utility from consumption becomes
$U(w-p_{0}-p_{i}^{t})$. The disutility function $C$ then represents the
participant’s difference in utility for consumption,

$C(p)=U(w-p_{0})-U(w-p_{0}-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:

$\textsc{Wel}^{{\mathbf{v}}}({\mathbf{x}},{\mathbf{p}})=\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{x}}_{i},{\mathbf{p}}_{i}).$

Following the interpretation of $C$ in terms of consumption utility $U$,
$\textsc{Wel}^{{\mathbf{v}}}({\mathbf{x}},{\mathbf{p}})$ represents the gain
in utility to all participants for a given allocation ${\mathbf{x}}$ and
payments ${\mathbf{p}}$, above the baseline total utility of
$n^{2}U(w-p_{0})$, obtained by each of the $n$ participants obtaining utility
$U(w-p_{0})$ for $n$ rounds. Among all possible matchings ${\mathbf{x}}$ and
payment profiles ${\mathbf{p}}\in\mathbb{R}^{n\times n}$, the optimal welfare-
outcome is given by the maximum-weight matching
${{\mathbf{x}}}^{*}=\operatorname*{argmax}_{{\mathbf{x}}}\sum_{i}{{\mathbf{x}}_{i}\cdot{\mathbf{v}}_{i}}$
and payments ${{\mathbf{p}}}^{*}=(0,\ldots,0)$, whose welfare is denoted
$\textsc{OPT}({\mathbf{v}})=\textsc{Wel}^{{\mathbf{v}}}({{\mathbf{x}}}^{*},{\mathbf{p}}^{*})$.

To quantify the inefficiency of a rosca outcome $({\mathbf{x}},{\mathbf{p}})$,
we study the approximation ratio
$\textsc{OPT}({\mathbf{v}})/\textsc{Wel}^{\mathbf{v}}({\mathbf{x}},{\mathbf{p}})$.
When rosca outcomes are equilibria of auctions, as in Section 3, this ratio is
also known as the price of anarchy (PoA).

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 inefficiency.
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 first- and second-price (equivalently, ascending- and descending-
price) auctions, as well as up-front all-pay-style 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-specific 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 $b_{i}$ 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 $p_{i}=\sum_{t}p_{i}^{t}$ when
context allows. We can further assume per-period payments remain fixed 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 $\hat{p}_{i}$ and rebates $\hat{r}_{i}$, with
$p_{i}=\hat{p}_{i}-\hat{r}_{i}$. Formally:

######  Definition 1.

In an up-front rosca with quasilinear participants, each participant $i$
submits a bid $b_{i}$, with ${\mathbf{b}}=(b_{1},\ldots,b_{n})$. Let $r_{i}$
denote the rank of participant $i$’s bid. Allocations are
$x_{i}^{t}({\mathbf{b}})=1$ if $t=r_{i}$ and $0$ otherwise. Participant $i$’s
gross payment is $\hat{p}_{i}({\mathbf{b}})=b_{i}$, and their rebate is
$\hat{r}_{i}({\mathbf{b}})=\sum_{i^{\prime}\neq i}b_{i^{\prime}}/(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 first step follows from Lemma A.20 of Syrgkanis and Tardos (2013):

######  Lemma 1.

With quasilinear participants, any Nash equilibrium ${\mathbf{b}}$ of any up-
front rosca with values ${\mathbf{v}}$ satisfies

$\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{b}})\geq\tfrac{1}{2}\textsc{OPT}({\mathbf{v}})-\sum\nolimits_{i}\hat{p}_{i}({\mathbf{b}}).$
(1)

The left hand side of (1) is the equilibrium welfare. It therefore suffices
for the second step to upper bound the gross payments on the right hand side.

######  Lemma 2.

Let ${\mathbf{b}}$ be a Nash equilibrium of an up-front rosca with quasilinear
participants and values ${\mathbf{v}}$. Then, for any participant $i$,
$\hat{p}_{i}({\mathbf{b}})\leq{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{b}})$.

###### Proof.

Assume for some $i$ that
$\hat{p}_{i}({\mathbf{b}})>{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{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:
$\hat{r}_{i}(0,{\mathbf{b}}_{-i})=\hat{r}_{i}({\mathbf{b}})>{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{b}})-\hat{p}_{i}({\mathbf{b}})+\hat{r}_{i}({\mathbf{b}})$.
∎

Since $\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{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
PoA at most $4$.

###  3.2 Sequential Roscas

We now consider roscas with separate sequentially-held first- or second-price
auctions for each pot as opposed to the single-auction format from the
previous section.

######  Definition 2.

A first-price rosca runs a first-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 $b_{i^{*}}^{t}$, then
$x_{i^{*}}^{t}=1$, $x_{i}^{t}=0$ for all other participants $i$. The gross
payments are $\hat{p}_{i^{*}}^{t}=b_{i^{*}}^{t}$ and $\hat{p}_{i}^{t}=0$
otherwise. The rebates are $\hat{r}_{i}^{t}=b_{i^{*}}^{t}/(n-1)$ for all
$i\neq i^{*}$.

######  Definition 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 participant $i^{*}$, with second-highest bid $b_{(2)}^{t}$, then
$x_{i^{*}}^{t}=1$, $x_{i}^{t}=0$ for all other participants $i$. The gross
payments are $\hat{p}_{i^{*}}^{t}=b_{(2)}^{t}$ and $\hat{p}_{i}^{t}=0$
otherwise. The rebates are $\hat{r}_{i}^{t}=b_{(2)}^{t}/(n-1)$ for all $i\neq
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 ${\mathbf{a}}=(a_{1},\ldots,a_{n})$, and denote by $b_{i}^{t}$
participant $i$’s bid in a round $t$.

As with up-front roscas, we first derive a tradeoff between utility and gross
payments, and second consider the impact of rebates. The sequential format
complicates both steps. Our first step will follow from a novel composition
argument, where we show that both first- and 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 first-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, first- and second-price roscas can be thought of as the
sequential composition $n$ single-item auctions, with a rule excluding past
winners. Formally:

######  Definition 4 (Round-Robin Composition).

Given a single-item auction $M$, the $n$-item round-robin composition of $M$
is a multi-round allocation mechanism for $n$ items using the following
procedure: During each round $t$, each participant $i$ who has not yet been
allocated an item submits a bid $b_{i}^{t}$. The mechanism then runs $M$ among
the remaining participants to determine the allocation and payments for that
round.

The following definition of smoothness, adapted from Syrgkanis and Tardos
(2013), lets us characterize both first- and 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 $b_{i}^{t}$, 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 round-robin composition.

######  Definition 5.

Let $M$ be a sequential single-bid auction. We say $M$ is
$(\lambda,\mu_{1},\mu_{2})$-smooth if for every value profile ${\mathbf{v}}$
and action profile ${\mathbf{a}}$, there exists a randomized action
$a_{i}^{*}(a_{i},{\mathbf{v}})$ for each $i$ such that:

$\displaystyle\sum\nolimits_{i}({\mathbf{v}}_{i}\cdot$
$\displaystyle{\mathbf{x}}_{i}(a_{i}^{*}(a_{i},{\mathbf{v}}),{\mathbf{a}}_{-i})-p_{i}(a_{i}^{*}(a_{i},{\mathbf{v}}),{\mathbf{a}}_{-i})\geq$
$\displaystyle\lambda\textsc{OPT}({\mathbf{v}})-\mu_{1}\sum\nolimits_{i}\hat{p}_{i}({\mathbf{a}})-\mu_{2}\sum\nolimits_{i}B_{i}({\mathbf{a}}),$

where $B_{i}({\mathbf{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 first-price 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 specifically to the rosca setting, that relies on values
decreasing in time. Our composition result follows the following useful
definition:

######  Definition 6.

A single-item mechanism $M$ with allocation rule ${\mathbf{x}}$ and payments
${\mathbf{p}}$ is strongly individually rational (IR) if (1) for every profile
of actions ${\mathbf{a}}$, $x_{i}({\mathbf{a}})=0$ only if
$\hat{p}_{i}({\mathbf{a}})=0$, and (2) there exists an action $\bot$ such that
for all $i$ and ${\mathbf{a}}_{-i}$, $\hat{p}_{i}(\bot,{\mathbf{a}}_{-i})=0$.

######  Lemma 3.

Let $M$ be a strongly individually-rational single-item mechanism. If $M$ is
$(\lambda,\mu_{1},\mu_{2})$-smooth for $\lambda\leq 1$ and
$\mu_{1},\mu_{2}\geq 0$, then its round-robin composition is
$(\lambda,\mu_{1}+1,\mu_{2})$-smooth as long as $v_{i}^{t}\geq v_{i}^{t+1}$
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 first- and second-price roscas are
respectively $(1-1/e,2,0)$ and $(1,1,1)$-smooth.

We next analyze the impact of rebates. If we assume 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 an overbidding assumption is necessary for second-price roscas, as is
often the case for auctions with second-price payments. The overbidding
assumption we require is as follows:

######  Definition 7.

Action profile ${\mathbf{a}}$ satisfies no-overbidding if
$B_{i}({\mathbf{a}})\leq{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$
for every participant $i$.

######  Theorem 2.

Let $M$ be a strongly IR, single-item auction that is
$(\lambda,\mu_{1},\mu_{2})$-smooth, with $\lambda\leq 1$. With quasilinear
participants, every no-overbidding Nash equilibrium of the corresponding
auction rosca with rebates has PoA at most $(2+\mu_{1}+\mu_{2})/\lambda$.

###### Proof.

Lemma 3 implies that the rosca is $(\lambda,1+\mu_{1},\mu_{2})$-smooth before
rebates. We can therefore write:

$\displaystyle\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})$
$\displaystyle\geq\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}(a_{i}^{*},{\mathbf{a}}_{-i})$
$\displaystyle\geq\sum\nolimits_{i}({\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}(a_{i}^{*},{\mathbf{a}}_{-i})-\hat{p}_{i}(a_{i}^{*},{\mathbf{a}}_{-i}))$
$\displaystyle\geq\lambda\textsc{OPT}({\mathbf{v}})-(1+\mu_{1})\sum\nolimits_{i}\hat{p}_{i}({\mathbf{a}})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
-\mu_{2}\sum\nolimits_{i}B_{i}({\mathbf{a}})$
$\displaystyle\geq\lambda\textsc{OPT}({\mathbf{v}})-(1+\mu_{1}+\mu_{2})\sum\nolimits_{i}B_{i}({\mathbf{a}})$
$\displaystyle\geq\lambda\textsc{OPT}({\mathbf{v}})-(1+\mu_{1}+\mu_{2})\sum\nolimits_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$

Since both $\sum_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})$ and
$\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$ are equal to
equilibrium welfare, the result follows. ∎

######  Corollary 1.

For quasilinear participants, any Nash equilibrium of the first-price rosca
satisfying no-overbidding has PoA at most $3e/(e-1)$.

######  Corollary 2.

For quasilinear participants, any Nash equilibrium of the second-price rosca
satisfying no-overbidding has PoA 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 first-price rosca where overbidding leads to welfare
loss.

######  Example 1.

Consider three participants, with ${\mathbf{v}}_{1}=(1,0,0)$,
${\mathbf{v}}_{2}=(2,2,0)$, and ${\mathbf{v}}_{3}=(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$.111This
example does not satisfy the refinement of subgame perfection, though our
welfare guarantees do not need this restriction.

Despite the loss exhibited in Example 1, we can obtain a constant price of
anarchy for first-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 equilibrium,
the participant who wins in the final 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 first-price rosca. Then:

$\hat{p}_{t}^{t}\leq
v_{t}^{t}+\tfrac{1}{n-1}\sum_{t^{\prime}=t+1}^{n}v_{t^{\prime}}^{t^{\prime}}(\tfrac{n}{n-1})^{t^{\prime}-t-1}.$

We provide the proof in the supplementary materials.

######  Theorem 3.

In any Nash equilibrium of the first-price rosca, the PoA is at most
$(2e+1)e/(e-1)$.

The result follows from summing the bounds on $\hat{p}_{i}({\mathbf{a}})$ from
Lemma 4, which can be arranged to obtain an upper bound of
$e\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$ of the total
gross payments. The theorem then follows from applying smoothness as before.

###  3.4 Extension to Nonlinear Utilities

In Appendix C, 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 ($\beta$) and lower ($\alpha$) bounds on the
slope $C^{\prime}$. We give performance guarantees which scale linearly with
the ratio $\beta/\alpha$. 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 beneficial, i.e., by swapping
rounds in the rosca (Mequanent 1996).

In this section, we formally define 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
${\mathbf{p}}^{t}$ 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:

######  Definition 8.

Given initial allocation ${\mathbf{x}}$ and payments ${\mathbf{p}}^{t}$ at
round $t$, a swap is given by a pair of participants $i$, $i^{\prime}$
assigned to rounds $j,j^{\prime}\geq t$, respectively, and a payment
$\hat{p}$. A swap is valid if
$v_{i}^{j^{\prime}}-C(p_{i}^{t}+\hat{p})>v_{i}^{j}-C(p_{i}^{t})$ and
$v_{i^{\prime}}^{j}-C(p_{i^{\prime}}^{t}-\hat{p})>v_{i^{\prime}}^{j^{\prime}}-C(p_{i^{\prime}}^{t}).$

Upon executing a swap, set $x_{i}^{j},x_{i^{\prime}}^{j^{\prime}}\leftarrow
0$, $x_{i}^{j^{\prime}},x_{i^{\prime}}^{j}\leftarrow 1$, $p_{i}^{t}\leftarrow
p_{i}^{t}+\hat{p}$, and $p_{i^{\prime}}^{t}\leftarrow p_{i}^{t}-\hat{p}$.

Note that with quasilinear participants, all valid swaps must strictly improve
allocative efficiency since $C(p)=p$. That is,
$v_{i}^{j^{\prime}}+v_{i^{\prime}}^{j}>v_{i}^{j}+v_{i^{\prime}}^{j^{\prime}}$,
and the validity of a swap does not depend on the initial payments
${\mathbf{p}}^{t}$. We then study roscas of the following form:

######  Definition 9.

A swap rosca starts from an initial allocation ${\mathbf{x}}$ and initial
payments ${\mathbf{p}}=\\{{\mathbf{p}}^{t}\\}_{t=1}^{n}$ of $0$ for each
participant and round. At each round $t=1,\ldots,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, Definition 9 executes all swaps in round $1$. In this
case, the resulting allocation is guaranteed to be stable to pairwise swaps.

######  Definition 10.

An allocation ${\mathbf{x}}$ is swap-stable if for all participants
$i,i^{\prime}$ assigned to $j,j^{\prime}$, we have that
$v_{i}^{j}+v_{i^{\prime}}^{j^{\prime}}\geq
v_{i}^{j^{\prime}}+v_{i^{\prime}}^{j}$.

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 $\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}$
strictly increases each swap and that the number of allocations is finite.

######  Theorem 4.

For quasilinear participants, the welfare approximation for every swap rosca
is at most $2$.

###### Proof.

Without loss of generality, assume that the welfare-optimal allocation assigns
each participant $i$ to be allocated the pot in round $i$, so the optimal
welfare is $\sum_{i}v_{i}^{i}$. Now let $\pi(i)$ denote the _round_ when
participant $i$ is allocated the pot in the swap rosca’s final allocation, and
$\pi^{-1}(i)$ the _participant_ allocated the pot in round $i$. Note that
$\pi$ and $\pi^{-1}$ are bijections. Furthermore, under quasilinear utilities,
all payments between participants are welfare-neutral, and hence the rosca
welfare is given by $\sum_{i}v_{i}^{\pi(i)}$.

For any participant $i$, note that swap-stability implies

$v_{i}^{\pi(i)}+v_{\pi^{-1}(i)}^{i}\geq v_{i}^{i}+v_{\pi^{-1}(i)}^{\pi(i)}\geq
v_{i}^{i}.$

Summing over all participants $i$, we get

$\sum\nolimits_{i}v_{i}^{\pi(i)}+\sum\nolimits_{i}v_{\pi^{-1}(i)}^{i}\geq\sum\nolimits_{i}v_{i}^{i}.$

Since $\pi$ and $\pi^{-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 efficiency. 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 non-linear
form. We find that the approximation ratio of these roscas in more typical
scenarios is significantly 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\rightarrow 1$,
$C(p;W,a)\rightarrow\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 $9$\- and
$30$-person roscas (typical sizes for small- and medium-sized roscas), and
compare three quantities: the optimal welfare under our selected value
profile, 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 first experiment fixes a profile of participant values and studies the
performance of swap roscas as the convexity parameter $a$ and starting wealth
$W$ vary. The value profile, comprised of $9$ participants, features $6$ with
cutoff values of the form $v_{i}^{t}=\overline{v}$ for all $i\leq\hat{t}$ for
some $\hat{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 profiles 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,\ldots,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.

Table 1: Swap Rosca Performance Under Different CRRA Parameters (OPT = 45, random baseline ratio = 1.601) |  | $\mathbf{W}$
---|---|---
|  | $\mathbf{1}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{4}$ | $\mathbf{5}$
$\mathbf{a}$ | $\mathbf{0}$ | 1.035 | 1.034 | 1.035 | 1.034 | 1.035
$\mathbf{0.1}$ | 1.121 | 1.119 | 1.070 | 1.067 | 1.063
$\mathbf{0.2}$ | 1.122 | 1.121 | 1.080 | 1.074 | 1.074
$\mathbf{0.3}$ | 1.122 | 1.119 | 1.118 | 1.086 | 1.081
$\mathbf{0.5}$ | 1.122 | 1.124 | 1.121 | 1.119 | 1.120
$\mathbf{0.75}$ | 1.122 | 1.122 | 1.123 | 1.121 | 1.121
$\mathbf{1}$ | 1.124 | 1.122 | 1.121 | 1.123 | 1.122
$\mathbf{1.5}$ | 1.123 | 1.123 | 1.122 | 1.122 | 1.123
$\mathbf{2}$ | 1.122 | 1.125 | 1.123 | 1.122 | 1.123

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 efficiency. 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 efficiency. Thus, approximation ratios improve
(decrease) with higher $W$. However, as convexity increases, the disincentive
to swap caused by convexity overcomes the benefit 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 profiles 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 $9$\- and $30$-person roscas. This allows us to study the way the
distribution of need across a population impacts rosca welfare. We find 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, significant for their
integral role in allocating financial resources worldwide. In this work, we
focus specifically on the allocative efficacy 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 specific 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 efficiency
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
is often experienced by economically vulnerable individuals (Abebe, Kleinberg,
and Weinberg 2020; Nokhiz et al. 2021). Ethnographic work shows that altruism
plays a significant 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, efficacy, and
robustness.

## References

  * Abebe, Kleinberg, and Weinberg (2020) Abebe, R.; Kleinberg, J. M.; and Weinberg, S. M. 2020.  Subsidy Allocations in the Presence of Income Shocks.  In _AAAI_ , 7032–7039.
  * Adams Dale and Canavesi (1992) Adams Dale, W.; and Canavesi, M. L. 1992.  Rotating savings and credit associations in Bolivia.  _Adams and Fitchett, Informal Finance in Low-Income Countries_.
  * Alabi, Alabi, and Akrobo (2007) Alabi, G.; Alabi, J.; and Akrobo, S. T. 2007.  The Role Of Susu A Traditional Informal Banking System In The Development Of Micro And Small Scale Enterprises (MSEs) In Ghana.  _International Business & Economics Research Journal (IBER)_, 6(12).
  * Amankwah et al. (2019) Amankwah, E.; Gockel, F. A.; Eric, O.-A.; and Nubuor, A. 2019.  Pareto superior dimension of rotating savings and credit associations (ROSCAs) in Ghana: Evidence from Asunafo North Municipality of Ghana.  _Journal of Economics Library_ , 6(4): 287–309.
  * Anderson and Baland (2002) 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, Baland, and Moene (2009) Anderson, S.; Baland, J.-M.; and Moene, K. O. 2009.  Enforcement in informal saving groups.  _Journal of development Economics_ , 90(1): 14–23.
  * Ardener (1964) 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.
  * Ardener and Burman (1995) Ardener, S.; and Burman, S. 1995.  Money-go-rounds: The importance of rotating savings and credit associations for women.
  * Aredo (2004) Aredo, D. 2004.  Rotating savings and credit associations: characterization with particular reference to the Ethiopian Iqqub.  _Savings and Development_ , 179–200.
  * Baland, Guirkinger, and Hartwig (2019) Baland, J.-M.; Guirkinger, C.; and Hartwig, R. 2019.  Now or later? The allocation of the pot and the insurance motive in fixed roscas.  _Journal of Development Economics_ , 140: 1–11.
  * Besley, Coate, and Loury (1993) Besley, T.; Coate, S.; and Loury, G. 1993.  The economics of rotating savings and credit associations.  _The American Economic Review_ , 792–810.
  * Besley, Coate, and Loury (1994) Besley, T.; Coate, S.; and Loury, G. 1994.  Rotating savings and credit associations, credit markets and efficiency.  _The Review of Economic Studies_ , 61(4): 701–719.
  * Bouman (1995a) Bouman, F. 1995a.  Rosca: On the Origin of the Species/Rosca: sur L’Origine du Phenomène.  _Savings and Development_ , 117–148.
  * Bouman (1995b) Bouman, F. J. 1995b.  Rotating and accumulating savings and credit associations: A development perspective.  _World development_ , 23(3): 371–384.
  * Calomiris and Rajaraman (1998) 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ée (2021) Chevée, A. 2021.  Mutual Aid in north London during the Covid-19 pandemic.  _Social Movement Studies_ , 1–7.
  * Dobzinski and Paes Leme (2014) Dobzinski, S.; and Paes Leme, R. 2014.  Efficiency guarantees in auctions with budgets.  In _International Colloquium on Automata, Languages, and Programming_ , 392–404. Springer.
  * Fang, Ke, and Zhou (2015) Fang, H.; Ke, R.; and Zhou, L.-A. 2015.  Rosca meets formal credit market.  Technical report, National Bureau of Economic Research.
  * Feldman et al. (2016) Feldman, M.; Immorlica, N.; Lucier, B.; Roughgarden, T.; and Syrgkanis, V. 2016\.  The price of anarchy in large games.  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , 963–976.
  * Hartline, Hoy, and Taggart (2014) Hartline, J.; Hoy, D.; and Taggart, S. 2014.  Price of anarchy for auction revenue.  In _Proceedings of the fifteenth ACM conference on Economics and computation_ , 693–710.
  * Kabuya (2015) Kabuya, F. I. 2015.  The rotating savings and credit associations (ROSCAs): Unregistered sources of credit in local communities.  _IOSR Journal of Humanities and Social Science_ , 20(8): 95–98.
  * Kesselheim, Kleinberg, and Tardos (2015) 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.
  * Kesselheim and Kodric (2018) Kesselheim, T.; and Kodric, B. 2018.  Price of Anarchy for Mechanisms with Risk-Averse Agents.  In _45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  * Klonner (2001) Klonner, S. 2001.  How Roscas perform as insurance.
  * Klonner (2002) Klonner, S. 2002.  Understanding Chit Funds: Prize Determination and the Role of Auction Formats in Rotating Savings and Credit Associations.  _New Haven, USA_.
  * Klonner (2003a) Klonner, S. 2003a.  Buying fields and marrying daughters: An empirical analysis of ROSCA auctions in a south Indian village.  _Available at SSRN 400220_.
  * Klonner (2003b) Klonner, S. 2003b.  Rotating savings and credit associations when participants are risk averse.  _International Economic Review_ , 44(3): 979–1005.
  * Klonner (2008) Klonner, S. 2008.  Private information and altruism in bidding ROSCAs.  _The Economic Journal_ , 118(528): 775–800.
  * Kovsted and Lyk-Jensen (1999) 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 (1993) Kuo, P.-S. 1993.  _Loans, bidding strategies and equilibrium in the discount-bid rotating credit association_.  Institute of Economics, Academia Sinica.
  * La Ferrara (2002) La Ferrara, E. 2002.  Inequality and group participation: theory and evidence from rural Tanzania.  _Journal of Public Economics_ , 85(2): 235–273.
  * Mequanent (1996) 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 et al. (2020) 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 et al. (2021) 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.
  * Ogujiuba, Jumare, and Stiegler (2013) Ogujiuba, K.; Jumare, F.; and Stiegler, N. 2013.  Challenges of microfinance access in Nigeria: Implications for entrepreneurship development.
  * Pasha and Dayrra (2016) Pasha, S. A. M.; and Dayrra, A. D. D. 2016.  Role of ‘Iqqubs’ in Private Business Start Up and Development of Smes with Reference to Arba Minch, Ethiopia.  _Journal of Social Welfare and Management_ , 8(2).
  * Raccanello and Anand (2009) Raccanello, K.; and Anand, J. 2009.  Health expenditure financing as incentive for participation in ROSCAs.  _Revista Desarrollo y Sociedad_ , (64): 173–206.
  * Romer (1996) Romer, D. 1996.  _Advanced macroeconomics_.  McGraw-Hill advanced series in economics. New York: McGraw-Hill Companies.  ISBN 9780070536678.
  * Roughgarden (2009) Roughgarden, T. 2009.  Intrinsic robustness of the price of anarchy.  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , 513–522.
  * Roughgarden, Syrgkanis, and Tardos (2017) Roughgarden, T.; Syrgkanis, V.; and Tardos, E. 2017.  The price of anarchy in auctions.  _Journal of Artificial Intelligence Research_ , 59: 59–101.
  * Sedai, Vasudevan, and Pena (2021) Sedai, A. K.; Vasudevan, R.; and Pena, A. A. 2021.  Friends and benefits? Endogenous rotating savings and credit associations as alternative for women’s empowerment in India.  _World Development_ , 145: 105515.
  * Smets (2000) Smets, P. 2000.  ROSCAs as a source of housing finance for the urban poor: An analysis of self-help practices from Hyderabad, India.  _Community Development Journal_ , 35(1): 16–30.
  * Syrgkanis and Tardos (2013) Syrgkanis, V.; and Tardos, E. 2013.  Composable and efficient mechanisms.  In _Proceedings of the forty-fifth annual ACM symposium on Theory of computing_ , 211–220.
  * Travlou (2020) Travlou, P. 2020.  Kropotkin-19: A Mutual Aid Response to COVID-19 in Athens.  _Design and Culture_ , 1–10.
  * Van den Brink and Chavas (1997) 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.

hello

##  Appendix A Further Related Works

Roscas are well-documented as both pervasive and effective in promoting
positive economic, social, and even health outcomes. Beyond works already
mentioned, Raccanello and Anand (2009) document the use of roscas to finance
healthcare expenditures and build wealth in Mexico. Aredo (2004) demonstrates
the flexible and varied nature of roscas in Ethiopia. Pasha and Dayrra (2016)
show that ekub are an engine of small business finance in the city of Arba
Minch, and that private businesses actually prefer raising money from roscas
than from formal financial institutions. Amankwah et al. (2019) and Alabi,
Alabi, and Akrobo (2007) study roscas in Ghana, Ogujiuba, Jumare, and Stiegler
(2013) in Nigeria, and Kabuya (2015) in Eswatini. Alabi, Alabi, and Akrobo
(2007) show from evidence in Ghana that people joined roscas for their
perceived efficiency, and that roscas facilitated small-scale business
enterprises.

Many studies analyze composition and participation differences across age,
ethic, gender, and socioeconomic lines. Adams Dale and Canavesi (1992) and
Ardener and Burman (1995) show that rosca participation is higher among women
than men. Anderson and Baland (2002) shows how employed married women in
particular in Kenya use roscas to save, protecting earnings from their
husbands’ more immediate-minded spending. Roscas are known to often include
members from similar socio-economic backgrounds (Aredo 2004). Nonetheless,
Klonner (2008) shows that intragroup diversity is associated with higher rates
of bidder altruism and more efficient intra-rosca allocations.

Economists have also studied the interaction of roscas with formal credit
markets. For instance, Besley, Coate, and Loury (1994) show that while credit
markets are more efficient than roscas, there are situations in which one can
expect a higher ex ante expected utility in roscas than formal credit markets.
Relatedly, Fang, Ke, and Zhou (2015) show that in cases where formal credit
markets are present but imperfect, roscas and credit markets can complement
one another, thereby improving social welfare.

A different line of work studies roscas as a form of insurance. Klonner (2001)
develops the first such model of roscas, comparing their performance to risk-
sharing contracts. In this model, roscas can serve as a financial intermediary
and benefit risk-averse participants. This work also analyzes the risk-sharing
performance of several bidding roscas run simultaneously. The conclusion is
that this set-up matches the performance of linear risk-sharing contracts
while boasting greater enforceability. Other studies of roscas as insurance
include Baland, Guirkinger, and Hartwig (2019), and Calomiris and Rajaraman
(1998).

This work is most closely related existing analyses of roscas’ efficiency.
Besley, Coate, and Loury (1993, 1994) introduce the first theoretical model of
roscas, and a strong focus these and of subsequent studies is on providing
comparative welfare guarantees, e.g. between different types of roscas, or
between roscas and alternative financial institutions. These results typically
require strong assumptions, e.g. on homogeneity values of either across
participants or over time. For example, Besley, Coate, and Loury (1993, 1994)
show that both the random and bidding rosca are inefficient, but do not give
bounds on this inefficiency. Kovsted and Lyk-Jensen (1999) analyze differences
between random and bidding roscas, again under the assumption that people are
saving for a large purchase. They allow for some heterogeneity in people’s
access to credit, and again provide a comparative welfare analysis between
bidding and random roscas. Our work paints a more complete picture by giving
quantified bounds on roscas’ inefficiency, even in the face of heterogeneity
of participants’ values across agents and across time.

Our results apply techniques from auction theory and the price of anarchy
literature. In particular, we make extensive use of smoothness, formalized in
Roughgarden (2009) and adapted to auctions in Syrgkanis and Tardos (2013).
Smoothness is a sufficient condition for approximately-optimal equilibrium
welfare, and is preserved by combination with other smooth mechanisms. In
addition, smoothness-derived guarantees generalize beyond standard
quasilinear, full-information settings to learning outcomes and Bayes-Nash
equilibria, revenue Hartline, Hoy, and Taggart (2014), large games Feldman et
al. (2016), risk-averse agents, Kesselheim and Kodric (2018), and more.
Roughgarden, Syrgkanis, and Tardos (2017) give an excellent survey. Notably,
because of the way payments are redistributed, smoothness is not sufficient
for approximately optimal welfare in roscas. To derive our welfare results, we
instead combine smoothness with extra analysis to control the impact of
redistribution on welfare.

##  Appendix B Missing Proofs and Examples

###  B.1 Swap Rosca Example

The example below shows that the bound from Theorem 1 is tight.

######  Example 2.

Suppose we have three participants with value vectors:
${\mathbf{v}}_{1}=(0,0,0)$, ${\mathbf{v}}_{2}=(1,0,0)$, and
${\mathbf{v}}_{3}=(1,1,0)$. The optimal allocation allocates the pot to
participant 2 in round 1, participant 3 in round 2, and participant 1 in round
3 for total welfare $\textsc{OPT}({\mathbf{v}})=2$. However, the initial
allocation that allocates the pot to participant 1 in round 2, participant 2
in round 3, and participant 3 in round 1 is swap-stable and has welfare $1$.

###  B.2 Proof of Lemma 3

See 3

###### Proof.

Given value profile ${\mathbf{v}}$, an optimal allocation is an assignment
from participants $i$ to pots $t^{*}_{i}$. For values $v$ and action profile
${\mathbf{a}}$ in the sequential mechanism, we construct a deviation
$a^{*}_{i}$ for each participant $i$ in the following way: participant $i$
simulates their equilibrium strategy up until round $t_{i}^{*}-1$. Then, in
round $t_{i}^{*}$, they play their smoothness deviation for $M$ on value
profile $\hat{\mathbf{v}}$ and action $a_{i}^{t}$ for $i$, where
$\hat{v}_{i}=v_{i}^{t}$ and $0$ for all other participants. They play $\bot$
in all subsequent rounds. Note that, in simulating $a_{i}$, participant $i$
may win in some round $\hat{t}_{i}\leq t^{*}_{i}$, in which case the mechanism
excludes them from future rounds.

Let $S_{\textsc{EQ}}$ denote the set of participants whose deviations cause
them to win before $t_{i}^{*}$ and let $S_{\textsc{OPT}}$ denote the set of
participants who do not win before $t^{*}_{i}$, hence are able to play their
smoothness deviation in round $t^{*}_{i}$. For participants in
$S_{\textsc{OPT}}$, the choice of smoothness deviation for round $t^{*}_{i}$
implies:

$\displaystyle{\mathbf{v}}_{i}\cdot$
$\displaystyle{\mathbf{x}}_{i}(a_{i}^{*},{\mathbf{a}}_{-i})-\hat{p}_{i}(a_{i}^{*},{\mathbf{a}}_{-i})$
$\displaystyle\geq\lambda\cdot
v_{i}^{t_{i}^{*}}-\mu_{1}\sum\nolimits_{k}\hat{p}_{k}^{t_{i}^{*}}({\mathbf{a}})-\mu_{2}\sum\nolimits_{k}B_{k}^{t_{i}^{*}}({\mathbf{a}}),$

where for any period $t$, $B_{k}^{t}({\mathbf{a}})$ is participant $k$’s bid
if they win in round $t$ and $0$ otherwise.

For participants in $S_{\textsc{EQ}}$, if $\hat{t}_{i}$ denotes the round they
win in equilibrium, then

${\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}(a_{i}^{*},{\mathbf{a}}_{-i})-\hat{p}_{i}(a_{i}^{*},{\mathbf{a}}_{-i})=v_{i}^{\hat{t}_{i}}-\hat{p}_{i}({\mathbf{a}})\geq
v_{i}^{t_{i}^{*}}-\hat{p}_{i}({\mathbf{a}}),$

where the inequality follows from the fact that values are nonincreasing over
time.

Summing over participants, we obtain:

$\displaystyle\sum_{i}$
$\displaystyle({\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}(a_{i}^{*},{\mathbf{a}}_{-i})-\hat{p}_{i}(a_{i}^{*},{\mathbf{a}}_{-i}))$
$\displaystyle\geq\lambda\textsc{OPT}({\mathbf{v}})-\mu_{1}\sum\limits_{i\in
S_{\textsc{OPT}}}\sum_{k}\hat{p}_{k}^{t_{i}^{*}}({\mathbf{a}})-\sum\limits_{i\in
S_{\textsc{EQ}}}\hat{p}_{i}({\mathbf{a}})$
$\displaystyle-\mu_{2}\sum\limits_{i\in
S_{\textsc{OPT}}}\sum_{k}B_{k}^{t_{i}^{*}}({\mathbf{a}}).$

The second and third terms on the righthand side of this inequality are each
at least the total payments of the sequential mechanism. For the last term, we
can write

$\sum\limits_{i\in
S_{\textsc{OPT}}}\sum_{k}B_{k}^{t_{i}^{*}}({\mathbf{a}})\leq\sum_{i}\sum_{t}B_{i}^{t}({\mathbf{a}})=\sum_{i}B_{i}({\mathbf{a}}),$

where the first line follows from the fact that participants’ bids are
nonnegative and the second line from the fact that participants win in at most
one round. We therefore obtain

$\displaystyle\sum\nolimits_{i}$
$\displaystyle({\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}(a_{i}^{*},{\mathbf{a}}_{-i})-\hat{p}_{i}(a_{i}^{*},{\mathbf{a}}_{-i}))$
$\displaystyle\geq\lambda\textsc{OPT}({\mathbf{v}})-(\mu_{1}+1)\sum\nolimits_{i}\hat{p}_{i}({\mathbf{a}})-\mu_{2}\sum\nolimits_{i}B_{i}({\mathbf{a}})$

giving us the desired inequality. ∎

The following example demonstrates the necessity of our no-overbidding
assumption.

######  Example 3.

Suppose participant $1$ has value $(10,0)$ and participant $2$ has value
$(0,0)$. If participant $2$ bids $10$ in round $1$, then participant $1$
cannot win without incurring negative utility. participant $2$ thus wins for
free and hence no rebates are distributed. The equilibrium welfare here is
$0$, whereas the optimal welfare is $10$.

###  B.3 Proof of Lemma 4

See 4

###### Proof.

In what follows, we index bidders so that in the optimal allocation,
participant $i$ wins in round $i$.

We suppress dependence of payments and allocations on the profile of
equilibrium bids when it is clear from context. We argue by strong induction
on the number of rounds remaining.

As our base case, note that participant $n$ could choose to bid $0$ and incur
nonnegative utility from round $n$.222Note that this is different from their
overall utility due to rebates in rounds $1$ through $n-1$. Also note that we
can, in fact, say $\hat{p}_{n}^{n}=0$, but the weaker argument above yields
cleaner indexing without changing the end constant. Their continuation utility
for playing according to their equilibrium strategy is
$v_{n}^{n}-\hat{p}_{n}^{n}\geq 0$, which yields the desired inequality for the
base case.

Now assume that for all rounds from $t+1$ onward, the desired inequality
holds. participant $t$ could choose to bid $0$ in all rounds starting with
$t$. The continuation utility from this deviation is at least $0$. Meanwhile,
in equilibrium, $t$ is receiving
$v_{t}^{t}-\hat{p}_{t}^{t}+\sum_{t^{\prime}=t+1}^{n}\hat{p}_{t^{\prime}}^{t^{\prime}}/(n-1)\geq
0$ from future rounds. We therefore can upper bound $\hat{p}_{t}^{t}$ by

$\displaystyle
v_{t}^{t}+\tfrac{1}{n-1}\sum_{t^{\prime}=t+1}^{n}\left[v_{t^{\prime}}^{t^{\prime}}+\tfrac{1}{n-1}\sum_{t^{\prime\prime}=t^{\prime}+1}^{n}v_{t^{\prime\prime}}^{t^{\prime\prime}}\left(\tfrac{n}{n-1}\right)^{\tau}\right],$

where $\tau=t^{\prime\prime}-t^{\prime}-1$. Collecting coefficients on
$v_{t^{\prime}}^{t^{\prime}}$ gives us the following equivalent upper bound:

$\displaystyle\hat{p}_{t}^{t}$ $\displaystyle\leq
v_{t}^{t}+\tfrac{1}{n-1}\sum_{t^{\prime}=t+1}^{n}v_{t^{\prime}}^{t^{\prime}}\left(1+\tfrac{1}{n-1}\sum_{j=0}^{t^{\prime}-t-2}\left(\tfrac{n}{n-1}\right)^{j}\right)$
$\displaystyle=v_{t}^{t}+\tfrac{1}{n-1}\sum_{t^{\prime}=t+1}^{n}v_{t^{\prime}}^{t^{\prime}}\left(1+\tfrac{1}{n-1}\tfrac{1-(\tfrac{n}{n-1})^{t^{\prime}-t-1}}{1-\tfrac{n}{n-1}}\right)$
$\displaystyle=v_{t}^{t}+\tfrac{1}{n-1}\sum_{t^{\prime}=t+1}^{n}v_{t^{\prime}}^{t^{\prime}}(\tfrac{n}{n-1})^{t^{\prime}-t-1}.\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \qed$

###### Proof of Theorem 3.

We first sum the bounds from Lemma 4:

$\displaystyle\sum_{i}\hat{p}_{i}({\mathbf{a}})$
$\displaystyle=\sum_{t=1}^{n}\hat{p}_{t}^{t}({\mathbf{a}})$
$\displaystyle\leq\sum_{t=1}^{n}\left[v_{t}^{t}+\tfrac{1}{n-1}\sum_{t^{\prime}=t+1}^{n}v_{t^{\prime}}^{t^{\prime}}(\tfrac{n}{n-1})^{t^{\prime}-t-1}\right]$
$\displaystyle=\sum_{t=1}^{n}\left(\tfrac{n}{n-1}\right)^{t-1}v_{t}^{t}$
$\displaystyle\leq
e\sum_{t=1}^{n}v_{t}^{t}=e\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}}).$

By Lemma 3, the first-price rosca is $(1-1/e,2,0)$-smooth before rebates.
Considering the same deviation strategy with rebates, we obtain,

$\displaystyle\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})$
$\displaystyle\geq\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}(a_{i}^{*},{\mathbf{a}}_{-i})$
$\displaystyle\geq\sum\nolimits_{i}({\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}(a_{i}^{*},{\mathbf{a}}_{-i})-\hat{p}_{i}(a_{i}^{*},{\mathbf{a}}_{-i}))$
$\displaystyle\geq(1-1/e)\textsc{OPT}({\mathbf{v}})-2\sum\nolimits_{i}\hat{p}_{i}({\mathbf{a}})$
$\displaystyle\geq(1-1/e)\textsc{OPT}({\mathbf{v}})-2e\sum\nolimits_{i}{\mathbf{v}}_{i}\cdot
x_{i}({\mathbf{a}})$

The result follows from noting that both
$\sum_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})$ and
$\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$ represent the
equilibrium welfare. ∎

##  Appendix C Extension to Nonlinear Utilities

In this appendix, we show how our auction results for up-front roscas and no-
overbidding sequential roscas extend to the more general setting of nonlinear
cost for money $C$. We consider the class of convex functions $C$ satisfying
$C(0)=0$ and $C^{\prime}(x)\in[\alpha,\beta]$ on the range of relevant values
for some $0<\alpha\leq\beta$, and we prove bounds which degrade linearly in
the ratio $\beta/\alpha$.If $C$ is allowed to be an arbitrary convex function,
then it could serve as a hard budget; auctions with hard budgets are known to
have unbounded PoA (Syrgkanis and Tardos 2013; Dobzinski and Paes Leme 2014).
Under this regime we can take advantage of two facts which follow immediately
from basic calculus:

######  Lemma 5.

Let $C$ be convex and increasing and satisfy $C^{\prime}(x)\in[\alpha,\beta]$
and $C(0)=0$, with $0<\alpha\leq\beta$.

Then:

  1. a.

For $x\geq 0$, $C(x)\in[\alpha x,\beta x]$.

  2. b.

For $x\leq 0$, $C(x)\in[\beta x,\alpha x]$.

As in the quasilinear case, we demonstrate our approach with up-front roscas,
then present the more involved analysis of sequential roscas. Both the
tradeoff step between utilities and payments and the upper bound on payments
need to be adjusted to accommodate nonlinear utilities.

###  C.1 Up-Front Roscas

Under quasilinear utilities, it was unimportant to the analysis whether
payments and rebates were made before round $1$ or distributed across time.
When utilities are nonlinear, recall that an participant $i$’s disutility for
payments is broken into the sum $\sum_{t}C(p_{i}^{t})$. Hence, the timing of
payments and rebates could change payoffs dramatically. Our analysis will be
agnostic to these timing considerations. Whatever the timing, we continue to
denote by $p_{i}^{t}({\mathbf{b}}),\hat{p}_{i}^{t}({\mathbf{b}})$, and
$\hat{r}_{i}^{t}({\mathbf{b}})$ the net payments, gross payments, and rebates,
respectively, of participant $i$ at time $t$ under bid profile ${\mathbf{b}}$.
Under any up-front rosca, participant $i$’s total payments are their bid.
Hence, $\sum_{t}\hat{p}_{i}^{t}({\mathbf{b}})=b_{i}$ and
$\sum_{t}\hat{r}_{i}^{t}({\mathbf{b}})=\sum_{j\neq i}b_{j}/(n-1)$.

Trading off payments and utilities becomes more complex. We extend the proof
from Syrgkanis and Tardos (2013), parameterizing by a constant $\rho$:

######  Lemma 6.

For any $\rho\in[0,2/\beta]$ and any Nash equilibrium ${\mathbf{b}}$ of an up-
front rosca with values ${\mathbf{v}}$:

$\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{b}})\geq(1-\tfrac{\rho\beta}{2})\textsc{OPT}({\mathbf{v}})-\tfrac{1}{\rho}\sum\nolimits_{i}\hat{p}_{i}({\mathbf{b}}).$

###### Proof.

Pick a player $i$, and consider the deviation bid $b_{i}^{*}\sim U[0,\rho
v_{i}^{t^{*}}]$, where $t^{*}$ denotes round $i$ is allocated in the optimal
assignment. Let $\hat{i}$ denote the participant who wins $t^{*}$ under
${\mathbf{b}}$. Then we can lower bound the deviation utility
$u_{i}^{{\mathbf{v}}_{i}}(b_{i}^{*},{\mathbf{b}}_{-i})$ as:

$\displaystyle\int_{0}^{\rho
v_{i}^{t^{*}}}\big{(}v_{i}^{t^{*}}x_{i}^{t^{*}}(b_{i}^{*},{\mathbf{b}}_{-i})-\sum_{t}C(p_{i}^{t}(b_{i}^{*},{\mathbf{b}}_{-i}))\big{)}/\rho
v_{i}^{t^{*}}\,db_{i}^{*}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \geq\int_{0}^{\rho
v_{i}^{t^{*}}}\big{(}v_{i}^{t^{*}}x_{i}^{t^{*}}(b_{i}^{*},{\mathbf{b}}_{-i})-C(b_{i}^{*})\big{)}/\rho
v_{i}^{t^{*}}\,db_{i}^{*}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \geq\int_{0}^{\rho
v_{i}^{t^{*}}}\big{(}v_{i}^{t^{*}}x_{i}^{t^{*}}(b_{i}^{*},{\mathbf{b}}_{-i})-\beta
b_{i}^{*}\big{)}/\rho v_{i}^{t^{*}}\,db_{i}^{*}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ =\int_{b_{\hat{i}}}^{\rho
v_{i}^{t^{*}}}\tfrac{1}{\rho}\,db_{i}^{*}-\tfrac{\beta\rho v_{i}^{t^{*}}}{2}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
=v_{i}^{t^{*}}-\tfrac{b_{\hat{i}}}{\rho}-\tfrac{\beta\rho v_{i}^{t^{*}}}{2}$

Summing the deviation utilities across participants yields the desired bound.
∎

To upper bound the impact of rebates, we use:

######  Lemma 7.

Let ${\mathbf{b}}$ be a Nash equilibrium of an up-front rosca. Then for any
participant $i$,
$\hat{p}_{i}({\mathbf{b}})\leq{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{b}})/\alpha$.

###### Proof.

Assume for some $i$ that
$\alpha\hat{p}_{i}({\mathbf{b}})>{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{b}})$.
Then $i$ could improve their utility by bidding $0$, which, in an up-front
rosca, does not change their rebates:
$\hat{r}_{i}(0,{\mathbf{b}}_{-i})=\hat{r}_{i}({\mathbf{b}})>{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{b}})-\alpha\hat{p}_{i}({\mathbf{b}})+\hat{r}_{i}({\mathbf{b}})\geq{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{b}})-\sum\nolimits_{t}C(\hat{p}_{i}^{t})+\hat{r}_{i}({\mathbf{b}})$.
∎

Combining Lemmas 6 and 7 and choosing $\rho$ as follows:

$\rho=\frac{\beta+\sqrt{\beta(2\alpha+\beta)}}{\beta(\alpha+\beta+\sqrt{\beta(2\alpha+\beta)})}$

yields the following price of anarchy bound:

######  Theorem 5.

With cost for money $C$ satisfying $C^{\prime}(x)\in[\alpha,\beta]$ every Nash
equilibrium of an up-front rosca has PoA at most:

$\textsc{PoA}\leq\frac{\alpha+\beta+\sqrt{\beta(2\alpha+\beta)}}{\alpha}.$

Note that the bound degrades linearly with the ratio $\beta/\alpha$, as
promised. Moreover, taking $\alpha=\beta=1$ slightly improves on the bound
from Theorem 1; several of the other constants in the paper can be improved
through similar optimization of the bid deviations. We eschewed such
optimization in favor of readability.

###  C.2 Sequential Roscas

We take a smoothness-based approach to sequential roscas. We will use the
following generalization, adapted to non-linear utilities:

######  Definition 11.

Let $M$ be a sequential single-bid auction. We say $M$ is
$(\lambda,\mu_{1},\mu_{2})$-smooth if for every value profile ${\mathbf{v}}$
and action profile ${\mathbf{a}}$, there exists a randomized action
$a_{i}^{*}(a_{i},{\mathbf{v}})$ for each $i$ such that:

$\displaystyle\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}(a_{i}^{*}(a_{i},{\mathbf{v}}),{\mathbf{a}}_{-i})$
$\displaystyle\,\,\,\geq\lambda\textsc{OPT}({\mathbf{v}})-\mu_{1}\sum\nolimits_{i}\hat{p}_{i}({\mathbf{a}})-\mu_{2}\sum\nolimits_{i}C(B_{i}({\mathbf{a}})),$

where $B_{i}({\mathbf{a}})$ is $i$’s bid in the round where they win, or $0$
if no such round exists.

First-and second-price auctions are smooth, via extensions of the arguments
from Syrgkanis and Tardos (2013).

######  Lemma 8.

The single-round second-price auction is $(1,0,1)$-smooth.

###### Proof.

Let $h$ be the index of the participant with the highest value. Have this
bidder bid $C^{-1}(v_{h})$, while the remaining participants bid $0$. Let
$i^{*}$ denote the index of the highest bidder in equilibrium, and $\hat{i}$
the index of the highest bidder other than $h$. (We may have $i^{*}=\hat{i}$.)
If $h$ wins bidding $C^{-1}(v_{h})$, their utility is
$v_{h}-C(a_{\hat{i}})=\text{OPT}-C(a_{\hat{i}})\geq\text{OPT}-C(a_{i^{*}})$.
Otherwise, they lose and earn utility $0$, while $a_{\hat{i}}\geq
C^{-1}(v_{h})$. It follows that
$\text{OPT}-C(a_{i^{*}})=v_{h}-C(a_{i^{*}})\leq v_{h}-C(a_{\hat{i}})\leq
v_{h}-C(C^{-1}(v_{h}))=0$. This implies the desired smoothness bound. ∎

######  Lemma 9.

The single-item first-price auction is
$((1-1/e^{\beta})\beta^{-1},1,0)$-smooth.

###### Proof.

The highest valued participant, say index $h$, can deviate to submitting a
randomized bid $a_{h}^{*}$ drawn from the distribution with density function
$f(x)=\tfrac{1}{v_{h}-\beta\cdot x}$ and support
$[0,(1-1/e^{\beta})v_{h}/\beta]$. The utility of the highest participant from
this deviation is:

$\displaystyle u^{v_{h}}_{h}(a_{h}^{*},{\mathbf{a}}_{-h})$
$\displaystyle=\int_{\max_{i\neq
h}a_{i}}^{\left(1-\frac{1}{e^{\beta}}\right)\frac{v_{h}}{\beta}}(v_{h}-C(x))f(x)dx$
$\displaystyle\geq\int_{\max_{i\neq
h}a_{i}}^{\left(1-\frac{1}{e^{\beta}}\right)\frac{v_{h}}{\beta}}(v_{h}-\beta\cdot
x)f(x)dx$
$\displaystyle=\left(1-\frac{1}{e^{\beta}}\right)\frac{v_{h}}{\beta}-\max_{i}a_{i}.$

Since all other bidders can get utility at least $0$ by e.g. bidding $0$, the
stated smoothness bound holds. ∎

Under the generalized definition of smoothness, the round-robin composition
result, Lemma 3 holds without modification. Hence, we obtain:

######  Corollary 3.

First-price roscas are $((1-1/e^{\beta})\beta^{-1},2,0)$-smooth, and second-
price roscas are $(1,1,1)$-smooth.

Under non-linear utilities, the appropriate notion of overbidding states that
no participant bids in a way that could yield negative utility. This
upperbounds their bids by an amount that depends on $C$:

######  Definition 12.

Action profile ${\mathbf{a}}$ satisfies no-overbidding if
$C(B_{i}({\mathbf{a}}))\leq{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$
for every participant $i$.

Under no-overbidding, values and payments cannot exceed utilities by too much,
as the following two Lemmas state.

######  Lemma 10.

In any no-overbidding profile ${\mathbf{a}}$ of sequential rosca based on a
strongly IR single-item auction:

$\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})\leq\tfrac{\beta}{\alpha}\sum_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}}).$

###### Proof.

By definition,
$\sum_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})=\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})-\sum_{i}\sum_{t}C(p_{i}^{t}({\mathbf{a}}))$.
The last term can be further decomposed as
$\sum_{i}\sum_{t}C(p_{i}^{t}({\mathbf{a}}))=\sum_{i}\sum_{t}C(\hat{p}_{i}^{t}({\mathbf{a}}))+\sum_{i}\sum_{t}C(-\hat{r}_{i}^{t}({\mathbf{a}}))$.
By the no-overbidding assumption,
$\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})\geq\sum_{i}\sum_{t}C(\hat{p}_{i}^{t}({\mathbf{a}}))$.
Hence, the the ratio of values to utilities is upper bounded by the ratio of
disutility from payments to utility from rebates. That is:

$\frac{\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})}{\sum_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})}\leq\frac{\sum_{i}\sum_{t}C(\hat{p}_{i}^{t}({\mathbf{a}}))}{-\sum_{i}\sum_{t}C(-\hat{r}_{i}^{t}({\mathbf{a}}))}.$

The lemma then follows from noting:

$\displaystyle\sum_{i}\sum_{t}C(\hat{p}_{i}^{t}({\mathbf{a}}))$
$\displaystyle\leq\beta\sum_{i}\sum_{t}\hat{p}_{i}^{t}({\mathbf{a}})$
$\displaystyle-\sum_{i}\sum_{t}C(-\hat{r}_{i}^{t}({\mathbf{a}}))$
$\displaystyle\geq\alpha\sum_{i}\sum_{t}\hat{p}_{i}^{t}({\mathbf{a}}).\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \qed$

######  Lemma 11.

In any no-overbidding profile ${\mathbf{a}}$ of sequential rosca based on a
strongly IR single-item auction:
$\sum_{i}\hat{p}_{i}({\mathbf{a}})=\sum_{i}\hat{r}_{i}({\mathbf{a}})\leq\alpha^{-1}\sum_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})$.

###### Proof.

By no-overbidding,
$\sum_{t}C(\hat{p}_{i}^{t})\leq{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$.
We may therefore write:

$\displaystyle\sum_{i}\hat{p}_{i}({\mathbf{a}})$
$\displaystyle=\sum_{i}\hat{r}_{i}({\mathbf{a}})$
$\displaystyle\leq\alpha^{-1}\sum_{i}\sum_{t}-C(-\hat{r}_{i}^{t}({\mathbf{a}}))$
$\displaystyle\leq\alpha^{-1}\Big{(}\sum_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
-\sum_{i}\sum_{t}C(\hat{p}_{i}^{t}({\mathbf{a}}))-\sum_{i}\sum_{t}C(-\hat{r}_{i}^{t}({\mathbf{a}}))\Big{)}$
$\displaystyle=\alpha^{-1}\sum_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}}),$

where the first inequality follows from upper bounding $C$, and the second
from no-overbidding. ∎

######  Theorem 6.

Let $M$ be a strongly IR, single-item auction that is
$(\lambda,\mu_{1},\mu_{2})$-smooth, with $\lambda\leq 1$. With quasilinear
participants, every no-overbidding Nash equilibrium of the corresponding
auction rosca with rebates has PoA at most
$(1+\mu_{1}\alpha^{-1}+\mu_{2}\beta\alpha^{-1})/\lambda$.

###### Proof.

The theorem follows from the inequalities below, justified after their
statement:

$\displaystyle\lambda\textsc{OPT}$
$\displaystyle\leq\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}(a_{i}^{*}(a_{i},{\mathbf{v}}),{\mathbf{a}}_{-i})+\mu_{1}\sum\nolimits_{i}\hat{p}_{i}({\mathbf{a}})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\mu_{2}\sum\nolimits_{i}\hat{C}(B_{i}({\mathbf{a}}))$
$\displaystyle\leq\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}(a_{i}^{*}(a_{i},{\mathbf{v}}),{\mathbf{a}}_{-i})+\tfrac{\mu_{1}}{\alpha}\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\mu_{2}\sum\nolimits_{i}\hat{C}(B_{i}({\mathbf{a}}))$
$\displaystyle\leq\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}(a_{i}^{*}(a_{i},{\mathbf{v}}),{\mathbf{a}}_{-i})+\tfrac{\mu_{1}}{\alpha}\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\mu_{2}\sum\nolimits_{i}{\mathbf{v}}_{i}\cdot{\mathbf{x}}_{i}({\mathbf{a}})$
$\displaystyle\leq\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}(a_{i}^{*}(a_{i},{\mathbf{v}}),{\mathbf{a}}_{-i})+\tfrac{\mu_{1}}{\alpha}\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\tfrac{\mu_{2}\beta}{\alpha}\sum\nolimits_{i}u_{i}^{{\mathbf{v}}_{i}}({\mathbf{a}}).$

The first inequality follows from smoothness. The second follows from Lemma
11, and the fourth from Lemma 10. The third inequality follows from no-
overbidding. Applying best response yields the result. ∎

We obtain price of anarchy bounds for second- and first-price rocscas as
corollaries. In particular, note that the price of anarchy is scale-invariant
with respect to $C$. That is, for any $\gamma>0$ and any equilibrium
${\mathbf{a}}$ with values ${\mathbf{v}}$, the same action profile
${\mathbf{a}}$ is also an equilibrium for values
$\hat{\mathbf{v}}=\gamma{\mathbf{v}}$ and cost function $\hat{C}(p)=\gamma
C(p)$. Hence, any bound proved for a scaling $\gamma\beta,\gamma\alpha$ of
$\beta,\alpha$ also holds for $\beta,\alpha$. Taking $\gamma=1/\beta$ implies
the promised linear dependencies:

######  Corollary 4.

Any Nash equilibrium of the second-price rosca satisfying no-overbidding has
PoA at most $1+2\beta/\alpha$.

######  Corollary 5.

Any Nash equilibrium of the first-price rosca satisfying no-overbidding has
PoA at most $(1+2\beta/\alpha)(1-1/e)$.

Note that our first-price result requires the no-overbidding assumption. We
leave open whether the less restrictive analysis of Section 3.3 can be
extended in some way to the nonlinear setting as well.

##  Appendix D Other Extensions for Auction Results

The smoothness framework is known to be robust to variations in equilibrium
assumptions, and we inherit this robustness to a significant degree. First, in
roscas and especially sequential ones, it is reasonable to assume that
participants may not best respond perfectly. A more natural notion may be some
form of $\epsilon$-best response, where participants maximize their utility up
to an additive $\epsilon$ error. All our results hold under this
generalization, with the welfare guarantees similarly degrading by an
additive, $O(n\epsilon)$ factor. Second, we may also want to study roscas
under incomplete information, with each participant’s values being drawn
according to a prior. Smoothness-based welfare results typically extend to
such settings, and ours do as well in large part. In particular, Theorems 1
and 2 both hold under any Bayes-Nash equilibrium where participants’ value
vectors are drawn independently of one another. For Theorem 2, this can be
derived directly by mimicking the proof of Theorem 4.3 in Syrgkanis and Tardos
(2013). The extension to Theorem 1 holds by additionally observing that in any
Bayes-Nash equilibrium of up-front rosca, no participant has an incentive to
overbid.

Unfortunately, our proof of Lemma 4 seems to rely on the full-information
assumption. We leave it as an open question whether a Lemma 4 can be extended
beyond full-information environments. Either way, among all auction settings,
roscas, where participants are typically members of tight-knit communities,
are maybe the best candidate for assuming full information.

##  Appendix E Experiment: CRRA Utilities (Extended)

Table 2: Value Profiles for 9-participant Roscas Used in CRRA Utilities
Experiment Profiles (Values in Rounds 1-9)
---
2 0 0 0 0 0 0 0 0
2 2 2 2 2 0 0 0 0
5 5 0 0 0 0 0 0 0
5 5 5 5 5 5 0 0 0
8 8 8 0 0 0 0 0 0
8 8 8 8 8 8 8 0 0
8 8 8 5 5 5 2 2 2
8 8 6 6 4 4 2 2 0
8 7 6 5 4 3 2 1 0

The value profiles for in our CRRA Utilities experiment in Section 4.3 are
provided in Table 2. Recall that these nine value profiles feature six with
cutoff values of the form $v_{i}^{t}=\overline{v}$ for all $i\leq\hat{t}$ for
some $\hat{t}$ and three participants with values that 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 repeat this experiment using a 30-participant rosca with qualitatively
similar value profiles as those used in the 9-participant setting: the 30
value profiles feature 20 with cutoff values of the form
$v_{i}^{t}=\overline{v}$ for all $i\leq\hat{t}$ for some $\hat{t}$ and 10
participants with values that are roughly linearly decreasing in time. The
average maximum value among cutoff participants is $15.5$, which is very close
to the average value for linearly decreasing values ($15$). Table 3 presents
the results of our CRRA Utilities experiment from Section 4.3 repeated in a
30-participant rosca. Once again, we observe the same trends as in the
9-participant rosca experiment, providing further evidence to strengthen the
observations and claims in Section 4.3.

Table 3: Swap Rosca Performance Under Different CRRA Parameters (OPT = 551, random baseline ratio = 1.580) |  | $\mathbf{W}$
---|---|---
|  | $\mathbf{1}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{4}$ | $\mathbf{5}$
$\mathbf{a}$ | $\mathbf{0}$ | 1.036 | 1.036 | 1.036 | 1.036 | 1.036
$\mathbf{0.1}$ | 1.105 | 1.104 | 1.087 | 1.086 | 1.085
$\mathbf{0.2}$ | 1.105 | 1.104 | 1.088 | 1.088 | 1.086
$\mathbf{0.3}$ | 1.104 | 1.104 | 1.105 | 1.090 | 1.089
$\mathbf{0.5}$ | 1.105 | 1.104 | 1.104 | 1.104 | 1.104
$\mathbf{0.75}$ | 1.104 | 1.104 | 1.105 | 1.104 | 1.104
$\mathbf{1}$ | 1.104 | 1.105 | 1.105 | 1.104 | 1.105
$\mathbf{1.5}$ | 1.104 | 1.104 | 1.105 | 1.105 | 1.105
$\mathbf{2}$ | 1.104 | 1.104 | 1.105 | 1.104 | 1.104

##  Appendix F Experiment: Distributional Diversity

Tables 5\- 6 summarize our second set of experiments, which vary the
composition of the population of participants in both $9$-participant and
30-participant roscas. More specifically, we consider seven different
configurations of value profiles, described briefly below and provided for the
9-participant rosca in Table 4 (qualitatively similar profiles were again used
for the 30-participant rosca, as in our CRRA Utilities experiments). All
participants have cutoff values, with participant $i$’s cutoff at $t=i$. We
then vary (a) the distribution of magnitudes for participants’ values and (b)
the correlation of an participant’s value with their cutoff round.
Distributions labeled “-dec” have values which are negatively correlated with
the cutoff round, and “-inc” have positively correlated values. The instance
“pointmass” gives all participants constant value up to their cutoffs. The
remaining instances can be described by the distribution of participants’
constant values before their cutoffs: “unif” has a distribution uniform on
$\\{1,\ldots,9\\}$, “pareto” a pareto distribution, and “unim” a unimodal
distribution with its mode at $4$. We further consider both quasilinear and
CRRA utilities.

Table 4: Value Profiles for 9-participant Roscas Used in the Distributional
Diversity Experiment

0 0 0 0 0 0 0 0 0
---
4 0 0 0 0 0 0 0 0
4 4 0 0 0 0 0 0 0
4 4 4 0 0 0 0 0 0
4 4 4 4 0 0 0 0 0
4 4 4 4 4 0 0 0 0
4 4 4 4 4 4 0 0 0
4 4 4 4 4 4 4 0 0
4 4 4 4 4 4 4 4 0
(a) pointmass

9 0 0 0 0 0 0 0 0
---
8 8 0 0 0 0 0 0 0
7 7 7 0 0 0 0 0 0
6 6 6 6 0 0 0 0 0
5 5 5 5 5 0 0 0 0
4 4 4 4 4 4 0 0 0
3 3 3 3 3 3 3 0 0
2 2 2 2 2 2 2 2 0
1 1 1 1 1 1 1 1 1
(b) unif-dec

0 0 0 0 0 0 0 0 0
---
1 1 0 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0
3 3 3 3 0 0 0 0 0
4 4 4 4 4 0 0 0 0
5 5 5 5 5 5 0 0 0
6 6 6 6 6 6 6 0 0
7 7 7 7 7 7 7 7 0
8 8 8 8 8 8 8 8 8
(c) unif-inc

12.7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
---|---|---|---|---|---|---|---|---
6.4 | 6.4 | 0 | 0 | 0 | 0 | 0 | 0 | 0
4.2 | 4.2 | 4.2 | 0 | 0 | 0 | 0 | 0 | 0
3.2 | 3.2 | 3.2 | 3.2 | 0 | 0 | 0 | 0 | 0
2.5 | 2.5 | 2.5 | 2.5 | 2.5 | 0 | 0 | 0 | 0
2.1 | 2.1 | 2.1 | 2.1 | 2.1 | 2.1 | 0 | 0 | 0
1.8 | 1.8 | 1.8 | 1.8 | 1.8 | 1.8 | 1.8 | 0 | 0
1.6 | 1.6 | 1.6 | 1.6 | 1.6 | 1.6 | 1.6 | 1.6 | 0
1.4 | 1.4 | 1.4 | 1.4 | 1.4 | 1.4 | 1.4 | 1.4 | 1.4
(d) pareto-dec

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
---|---|---|---|---|---|---|---|---
1.6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
1.8 | 1.8 | 0 | 0 | 0 | 0 | 0 | 0 | 0
2.1 | 2.1 | 2.1 | 0 | 0 | 0 | 0 | 0 | 0
2.5 | 2.5 | 2.5 | 2.5 | 0 | 0 | 0 | 0 | 0
3.2 | 3.2 | 3.2 | 3.2 | 3.2 | 0 | 0 | 0 | 0
4.2 | 4.2 | 4.2 | 4.2 | 4.2 | 4.2 | 0 | 0 | 0
6.4 | 6.4 | 6.4 | 6.4 | 6.4 | 6.4 | 6.4 | 0 | 0
12.7 | 12.7 | 12.7 | 12.7 | 12.7 | 12.7 | 12.7 | 12.7 | 0
(e) pareto-inc

7.2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
---|---|---|---|---|---|---|---|---
5.6 | 5.6 | 0 | 0 | 0 | 0 | 0 | 0 | 0
5.6 | 5.6 | 5.6 | 0 | 0 | 0 | 0 | 0 | 0
4.0 | 4.0 | 4.0 | 4.0 | 0 | 0 | 0 | 0 | 0
4.0 | 4.0 | 4.0 | 4.0 | 4.0 | 0 | 0 | 0 | 0
4.0 | 4.0 | 4.0 | 4.0 | 4.0 | 4.0 | 0 | 0 | 0
2.4 | 2.4 | 2.4 | 2.4 | 2.4 | 2.4 | 2.4 | 0 | 0
2.4 | 2.4 | 2.4 | 2.4 | 2.4 | 2.4 | 2.4 | 2.4 | 0
0.8 | 0.8 | 0.8 | 0.8 | 0.8 | 0.8 | 0.8 | 0.8 | 0.8
(f) unim-dec

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
---|---|---|---|---|---|---|---|---
2.4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
2.4 | 2.4 | 0 | 0 | 0 | 0 | 0 | 0 | 0
4.0 | 4.0 | 4.0 | 0 | 0 | 0 | 0 | 0 | 0
4.0 | 4.0 | 4.0 | 4.0 | 0 | 0 | 0 | 0 | 0
4.0 | 4.0 | 4.0 | 4.0 | 4.0 | 0 | 0 | 0 | 0
5.6 | 5.6 | 5.6 | 5.6 | 5.6 | 5.6 | 0 | 0 | 0
5.6 | 5.6 | 5.6 | 5.6 | 5.6 | 5.6 | 5.6 | 0 | 0
7.2 | 7.2 | 7.2 | 7.2 | 7.2 | 7.2 | 7.2 | 7.2 | 0
(g) unim-inc

We first note that as in the previous experiment, swap roscas provided across-
the-board improvements over both the worst-case ratios and those of random
allocation, and that under CRRA utilities, the social welfare degraded
slightly compared to quasilinear. Beyond these observations, we can glean
further insights from pairwise comparisons. Distributions labeled “-dec”
represent settings where higher-valued participants have more urgent need for
allocation. Both random allocation and swap roscas (under CRRA utilities)
perform poorly on these instances compared to their “-inc” counterparts,
whereas swap roscas (under quasilinear utilities) achieved better (lower)
performance ratios. Swap rosca welfares were roughly double those of the
random allocations (i.e., swap roscas achieved performance ratios that were
half those of random allocations). A second informative set of comparisons is
between “pointmass” and the “unim” distrbutions. Under both quasilinear and
CRRA utilities, the approximation ratio seems to be driven by the correlation
between urgency and value much more than the level of inequality in needs: if
the latter was the main concern, both “unim” distributions would see worse
performance. Swap roscas seem well-equipped to coordinate allocation among
heterogeneous participants.

Table 5: Swap Rosca Performance Under Diverse Value Distributions (9 participants). CRRA parameter values $W=4$, $a=.5$ Profile | OPT | Random | Quasilinear | CRRA
---|---|---|---|---
pointmass | 32 | 2.002 | 1.220 | 1.220
unif-dec | 45 | 2.452 | 1.000 | 1.327
unif-inc | 36 | 1.351 | 1.030 | 1.031
pareto-dec | 35.994 | 2.828 | 1.000 | 1.451
pareto-inc | 34.580 | 1.485 | 1.096 | 1.106
unim-dec | 36 | 2.337 | 1.116 | 1.310
unim-inc | 35.2 | 1.708 | 1.138 | 1.141
Table 6: Swap Rosca Performance Under Diverse Value Distributions (30 participants). CRRA parameter values $W=4$, $a=.5$ Profile | OPT | Random | Quasilinear | CRRA
---|---|---|---|---
pointmass | 116 | 2.002 | 1.218 | 1.218
unif-dec | 465 | 2.819 | 1.000 | 1.385
unif-inc | 435 | 1.452 | 1.043 | 1.058
pareto-dec | 399.499 | 4.000 | 1.000 | 1.757
pareto-inc | 396.165 | 1.323 | 1.066 | 1.061
unim-dec | 400 | 2.553 | 1.098 | 1.347
unim-inc | 398.667 | 1.636 | 1.114 | 1.114

##  Appendix G Simulation Code

All code used for simulations can be found at:
github.com/cikeokwu/swap_rosca_sims