# Bandit based centralized matching in two-sided markets for peer to peer
lending

Soumajyoti Sarkar Arizona State University<EMAIL_ADDRESS>
###### Abstract

Sequential fundraising in two sided online platforms enable peer to peer
lending by sequentially bringing potential contributors, each of whose
decisions impact other contributors in the market. However, understanding the
dynamics of sequential contributions in online platforms for peer lending has
been an open ended research question. The centralized investment mechanism in
these platforms makes it difficult to understand the implicit competition that
borrowers face from a single lender at any point in time. Matching markets are
a model of pairing agents where the preferences of agents from both sides in
terms of their preferred pairing for transactions can allow to decentralize
the market. We study investment designs in two sided platforms using matching
markets when the investors or lenders also face restrictions on the
investments based on borrower preferences. This situation creates an implicit
competition among the lenders in addition to the existing borrower
competition, especially when the lenders are uncertain about their standing in
the market and thereby the probability of their investments being accepted or
the borrower loan requests for projects reaching the reserve price. We devise
a technique based on sequential decision making that allows the lenders to
adjust their choices based on the dynamics of uncertainty from competition
over time. We simulate two sided market matchings in a sequential decision
framework and show the dynamics of the lender regret amassed compared to the
optimal borrower-lender matching and find that the lender regret depends on
the initial preferences set by the lenders which could affect their learning
over decision making steps.

##  1 Introduction

Sequential decision making in two sided markets like consumers and producers
has been part of bidding in e-commerce platforms like eBay, eBid for a very
long time. Not only that, P2P platforms like Prosper in the past allowed
lenders to bid on projects for peer microlending until they switched to posted
price mechanism [11]. However, for most peer microlending platforms like Kiva,
LendingClub among others, sequential decision making among lenders is obscure.
On the other hand single investor organizations like venture capitals have a
monopoly on who they fund 111https://www.inc.com/christine-lagorio/sam-altman-
yc-monopoly.html and this eludes any competition among multiple lenders over
borrowers. In this paper, we therefore attempt at abstract peer lending models
using matching markets. There are three keys points we address in this paper:
first, matching markets assume that the agents know their preferences over
each other [38], however in peer lending platforms, the lender investments
depend on a lot of factors like the return on investment, lender portfolio
interests, uncertainty on borrower project success [47]. To overcome this
assumption, we introduce sequential decision making so as to allow lenders to
adjust their preferences by learning them over time.

Secondly, the implicit nature of matching causes competition among agents on
both side - the borrowers trying to raise money from the same set of investors
while the investors trying to invest in the selected projects. This nature of
competition in markets for resolving conflicts has been studied recently [32]
where the agent preferences on one side are concealed from the other and so
the sequential decision aspect comes into play for preference revisions over
time. As mentioned, in such P2P platforms, there are mainly two sides to the
market: the borrowers who want to borrow money from others for their projects
or startups and the lenders who lend money to borrowers. The traditional rule
has been that these sides involve in two sided trading following the Dutch
Auction Mechanism [29, 46]. However, we assume that the matching in our case
is done based on a set of constraints and thre is no bidding from lenders in
that each lender has a fixed budget which is the same for all borrower
projects.

Finally, in an online setting, the learning step involves optimizing for the
lender’s utility or its valuation. However, this can be different from the
rewards that the system provides to the lender on a successful match. There
have been recent studies that try to address this gap between what the lender
estimates and what it receives as reward in an online setting [27]. To
address, this we devise a mechanism to tie the rewards from the agents to
their utility in an attempt to understand the dynamics of regret over time.
Centralized platforms to tackle these issues could ensure that the
transactions between borrowers and lenders are not only based on the money
that an investor is willing to put and its preferences but a borrower’s
willingness to accept the investment (these could be due to issues in lender
terms222https://siliconhillslawyer.com/2019/03/03/standard-term-sheets-
problem-yc/ or borrower’s assessment of the investor profile). As an added
caveat, it also allows for potential bias mitigation that can be implicit in
such platforms [41].

From the lender’s perspective, the main signals of interest then constitute
the probability of winning the bid, the probability of the loan being fully
funded, as well as the returns from the investment. In keeping with these
expectations, often the borrower’s interests are sidelined as it is assumed
that its only expectation from the platform and from investors is to get its
project or startup funded. For the rest of the paper, we lay the foundations
of our ongoing work that demonstrates a way to address competition and fair
play in such peer lending platforms with ideas from matching markets[39]. The
rest of the paper discusses some choices that could be made towards
formulating the utilities on both sides, the mechanism for sequential decision
making over rounds, and finally the tradeoff between the preference revisions
and the utilities for the agents which are also tied in some ways. Throughout
the paper, we consider agents are not strategic and therefore their preference
submissions are honest.

##  2 Related Work

In this section, we start by laying out the motivations behind the research
conducted in this study and the several studies done previously that are
closely tied to our problem. The problem we study has been split evenly in the
economics literature as well as the computer science discipline and we
describe the related studies in three categories:

1\. Peer lending in markets: Peer lending has been studied for platforms like
Prosper which in its earlier days would allow users to bid on the projects.
Earlier studies on this was conducted in [16, 15, 14] where algorithms were
designed for allocations of the social lending market that ensure stability
and Pareto optimality consider equitable allocations among equal borrowers.
These initial studies studied the static co-existence of borrowers and lenders
without changing outcome beliefs from the agents in the market which we
address in this paper. In these studies, characterization of the Nash
equilibria of the allocation mechanism was also conducted and disparities
among the allocations with respect to borrower repayments. In our paper, we
mainly focus on the uncertainty aspect of the market lenders and we try to
understand the lender regrets when we optimize for lender and borrower
utilities which can change over time unlike the studies mentioned. Dynamic
Matching Market Design has been an area that has received attention in the
past with studies [3] characterizing dynamic matching in networked markets,
where agents arrive and depart stochastically. Contrasting this, in this
research we consider the co-existence of lenders and borrowers in a market
without any stochastic shifts in lenders. One of the main motivations behind
this work has been the recent work conducted in [32] which designed the notion
of competition between agents in a matching market especially when one side of
the market is uncertain about its preferences on the other side of the market.
There have been other studies extending this framework especially in [40]
which consider uniform valuation in demand side agents in the market and
propose a decentralized version of the market that does not require knowledge
of the time horizon or the suboptimality gaps for the system to be in
equilibrium or the agents to reach stable matching. In our study, we consider
different settings than considered in these studies in that firstly we do not
consider global rankings of demand side agents among the supplier side agents.
Instead all agents on one side have unique preferences for the agents on the
other side. In this view, it becomes more difficult to design algorithms that
can provably reach equilibrium. We consider the case of many-one matching
where each lender is able to pick only one arm at each round. However, this
model can be extended to the situation of many-many matching where each lender
is able to pull multiple arms at each round. Our model is closely related to
the study in [35] of many-to-one matching markets in which agents with multi-
unit demand aim to maximize a cardinal linear objective subject to
multidimensional knapsack constraints.

2\. Bandits and bidding: The idea of decision making under uncertainty for
matching agents with budgets and preferences enjoy a rich literature in the
field of multi-armed bandit (MAB) settings. Our model for adapting this
framework of competing agents in matching markets for lending is motivated in
part by the idea of dynamic pricing with limited supply [4] where we we may
have multiple products for sale, with a limited supply of each product. There
have been studies that have proposed solving this problem in the realm of
knapsack settings [2, 5]. In these settings, at each round, the agents consume
some resources as outcomes and get a reward which are accumulated over time.
However in our settings, we assume the general MAB scenario where each round
is a new matching and the agents learn their preferences over the rounds
instead of allocations which are disbursed over time. Our settings are more
closely aligned to ad allocation with budgets which have several studies
associated to the exploration and exploitation settings of the ad allocation
mechanism that considers the rewards allocated to advertisers[24, 20]. The
second are where our work is related in the field of bandits and auctions is
the area of multi player bandits where the utilities of players impact the
decision outcomes. This setting of utilities is considered more heavily in the
economics literature and the general purview of bandits evade such utility
settings. Recently, there have been studies in the field of multi-layer bandit
settings [7] in which the reward of a player is a stochastic function of the
decisions of other players that operate in the same environment. The goal
there is to design a distributed algorithm that learns the matching between
players and arms that achieves max-min fairness while minimizing the regret.
Such applications of fairness constraints in the choice of arms have also been
considered in [28] where fairness precludes a worse agent being never favored
over a better one, despite a learning algorithm’s uncertainty over the true
payoffs. Fairness in two sided markets includes settings where producer-
consumer allocations are jointly optimized [36, 13]. We consider a version of
fairness in our work where we minimize some objective capturing the
discrepancies in allocation of resources among different borrowers.

3\. Recommendation systems and matchings: Bandits have been used in
recommendation systems for crowdfunding before. In a recent work on firing
bandits [26], the authors demonstrate a way to recommend projects to investors
in a way that maximizes the number of projects that reach the funding goal.
However, these studies do not take into account the preferences of the agents
while proposing the recommendation strategy. One of the problems that come
along with recommendation systems and their abstraction with matching markets
[45, 12] is the gap between the utility of the agents and the regret that
comes with the optimization objective of the recommendation systems. To this
end, recent studies [18] have focused on formal studies understanding the gap
between utility maximization and regret minimization. In our work, we tackle
this challenge by connecting the utilities of the agents with the regret the
system computes over time. Utility based constrained matching optimization for
recommendation systems have been a subject of research [34] where the
formulation includes the constraints of consumers needing to maintain certain
levels of engagement to stay in the system. Finally, user preferences in
recommendation systems have been a key factor behind their successes and
exploitations in item recommendations create a bias feedback loop [42] which
can be solved using sequential decision making settings.

Table 1: Table of Symbols Symbol |  Description
---|---
$b$($\mathcal{B}$), $l$($\mathcal{L}$) |  borrower (set of of borrowers), lender (set of lenders)
$c_{b}$, $q_{l}$ |  borrower $b$’s request amount, lender $l$’s budget
$u_{b}(l),u_{l}(b)$ |  borrower $b$’s utility from lender $l$, $l$’s utility from $b$
$\mathbf{Z}$ |  a matching such that $z_{bl}$=1 if $b$ is matched to $l$
$m_{z}(l)$, $m_{z}(b)$ |  denotes the borrower $\in\mathcal{B}$ matched to $l$, set of lenders matched to $b$
$t$ |  time step
$\mathcal{M}_{\mathcal{L}}$, $\mathcal{M}_{\mathcal{B}}$ |  dictionary mapping lenders to borrowers, dictionary mapping borrowers to sets of lenders
$X_{l,t}(b)$ |  random outcome or reward of the lender $l$ from $b$ at time step $t$
$\mu_{l}(b)$ |  empirical mean of the $b$-$l$ pair utility including the $u_{l}$ and borrower rewards $X_{l}$
$T_{b,l}(t)$ |  the number of times borrower $b$ was matched to lender $l$ till time $t$.
$cu_{l}(b),cl_{l}(b)$ |  Upper Confidence Bound (UCB) estimate of the lender utility $l$ from borrower $b$, Lower Confidence Bound for the same.

##  3 Problem Statement and Technical preliminaries

Our model of lending through a market matching perspective is very close to
the Shapley-Shubik model of bilateral trade with indivisible goods [44] where
there is a set of buyers or bidders (the lenders in our case) and a set of
sellers selling a unit of good (borrowers in our case) and no lender wants
more than one unit of the good. There is a monetary value that a buyer assigns
to the seller’s good and this relates to the amount of money that a lender is
willing to lend to a borrower posting in our case despite what the borrower
project funding requirements (which are generally more than an individual
lender can contribute) are. In the rest of the paper, we will denote matrices
using bold capital symbols, and vectors with bold lower cased symbols in the
rest of the paper. A summary of the important symbols can be references in
Table 1. In this section, we lay out the desiderata for our problem to set the
stage for the matching framework.

Borrowers and Lenders: Keeping the above in mind, we model the lending
platform as a market with 2 sides - the lenders denoted by the set of agents
$\mathcal{L}$ = $\\{l_{1},l_{2},\ldots l_{N}\\}$ and the borrowers denoted by
the set of arms $\mathcal{B}$ = $\\{b_{1},b_{2},\ldots b_{K}\\}$ and we assume
that $K\leq N$. We now have a two-sided market where the agents or arms on the
borrower side each have their own funding request proposals and their
corresponding requested amount which we denote by $c_{b}$, where
$b\in\mathcal{B}$. Similarly, the lenders each have an overall budget $q_{l}$,
where $l\in\mathcal{L}$. In addition, each set of agents on one side of the
market have the opportunity to submit their preferred rankings of the agents
on the other side of the market to the platform or the designer. These
preferences can be conflicting - many lenders might prefer to lend to the same
borrower, while multiple borrowers may prefer to tie up with the same lenders
having specific portfolio and interests.

Desiderata for Matching: As mentioned above, we consider the case of many-one
matching to simplify our settings similar to work done in [8], however our
framework can be easily extended to the many-many setting albeit with more
constraints. Each lender $l$ can be matched to at most one borrower while each
borrower $b$ can be matched to multiple lenders based on the amount $c_{b}$
requested. Such mechanisms are currently followed in platforms like GoFundMe
or Prosper Full Coverage lending model where the borrower only gets the
project funded when the sum of amounts lent, match or exceed the requested
amount

We consider that matching happens over multiple time steps and the lender is
allowed to explore its options to realize its best matching over time. At each
time step $t$, each lender $l_{i}$ is matched to a borrower $b_{j}$ and the
lender receives a stochastic valued reward drawn $\hat{\mu}_{b}(l)$ $\in(0,1)$
independent of all other rewards. The borrower or arm means
$\mu_{l}(b)_{b\in\mathcal{B},l\in\mathcal{L}}$ are heterogeneous across
lenders. Additionally, we also assume that for each lender $l$, the set of
mean $\mu_{l}(b)_{b\in\mathcal{B}}$ are all distinct. We denote by $m_{l}(t)$
to be the borrower assigned to $l$ at time step $t$. We maintain a utility
matrix $\mathbf{U_{b}}=\\{\mathbf{u_{b_{1}}},\mathbf{u_{b_{1}}},\ldots\\}$ of
dimension $K\times N$ that stores each arm’s utility from the lenders.
Similarly we maintain another matrix $\mathbf{U_{l}}$ of dimension $N\times K$
that stores the lender’s utilities from the borrowers. In an auction scenario
like the first price auction, this utility for the lender would be similar to
the difference between the valuation and the bid. One of the significant
points to note here is the gap between the lender’s own utility estimate
$u_{l}(b)$ for a borrower and the reward it receives $\hat{\mu}_{l}(b)$ if it
is matched at a time step. The goal of the borrower-lender matching is to find
an assignment of $m_{l,t}\in\mathcal{B}$ for all lenders $l\in\mathcal{L}$ at
each $t$ pertaining to constraints based on these utilities and rewards which
will be described in details in the next sections. We will often drop the time
step symbol $t$ from the notations when we generalize the operation whose
outcome is stored in the symbol to all time steps.

##  4 Key Ideas and intuition

In terms of the market design for two sided lending, there are three aspects
that control how the transactions are performed in the centralized version of
our matching design:

  * •

Utilities: Traditionally, most lending platforms have differentiated between
agent utilities and the platform objective of recommendation or matching.
However, what is often missing from these static objectives is the concept of
utility-driven returns. What it means is that the factor of the lenders on the
success of the borrower projects extends beyond just the monetary transaction
aspect but the overlap between the interests of the lender, the lender
contributions in terms of certain externalities, the egalitarian aspect of
market sharing in terms of fairness. So agent utilities (and this is in
addition to the agent preferences in our model) also decides how the matching
is made and this aspect in machine learning has been studied in terms of
credit scoring recently [31].

  * •

Matching Market Model: As one of the key components of our lending, we
abstract the resource allocation strategy between the borrowers and sellers in
the form of the traditional matching market model but with added constraints.
We assume that the lenders and borrowers do not know each other’s preferences
throughout the time which is in contrast to most matching markets.

  * •

Sequential decision making: This notion of interactive matching between two
sides of a market has been studied within the framework of unknown preferences
amongst the sides to the algorithm [22] in an online setting. This popularly
known setting called the bandit setting is a framework used to learn
preferences under uncertainty.

###  4.1 Matching objective

In lieu with the above desiderata, the matching platform takes as input the
ranking preferences of the borrowers and the lenders in the form of the
utility functions of the borrowers and the lenders prior to each time step. At
each time step, the platform solves a multi-objective optimization problem
that aims at matching the borrowers and the lenders. To decide a matching
between $\mathcal{B}$ and $\mathcal{L}$, we introduce the binary decision
variable $\mathbf{Z}$ := $(z_{bl})_{(b,l)\in\mathcal{B}\times\mathcal{L}}$
such that $z_{bl}$ = 1 if the loan from lender $l$ is assigned and accepted by
borrower $b$ and 0 otherwise. So
$\mathbf{Z}\in\\{0,1\\}^{|\mathcal{B}|\times|\mathcal{L}|}$ is a matching.
This gives rise to a policy that automatically matches a borrower and lender
based on this optimization problem and the lender $l$ receives the reward
$X_{l,t}$ for being matched to borrower $b$. We will discuss about the reward
structure $X_{l,t}$ in the following sections. In our bandit setting, the
lender $l$ is unable to observe the outcomes of other lenders nor the lenders
matched to $b$. To simplify our settings, we make the following assumptions:

  1. 1.

All utilities $u_{b}(l)$ and $u_{l}(b)$ are non-negative $\forall
b\in\mathcal{B},l\in\mathcal{L}$.

  2. 2.

for a lender $l$, $u_{b}(l)$ $\neq$ $u_{b^{\prime}}(l)$, for $b\neq
b^{\prime}$ and similarly, for a borrower $b$, $u_{l}(b)$ $\neq$
$u_{l^{\prime}}(b)$, for $l\neq l^{\prime}$.

The borrower-lender pair $(b,l)$ yields a total utility of
$u_{bl}:=u_{b}(l)+u_{l}(b)$. Recall that we consider a many-one matching where
each borrower is matched to many lenders and each lender is matched to only
one borrower. The preference orders of the borrowers and the lenders can be
captured in the following way: $b\succ_{j}b^{\prime}\Longleftrightarrow
u_{j}(b)>u_{j}(b^{\prime})$ and $l\succ_{i}l^{\prime}\Longleftrightarrow
u_{i}(l)>u_{i}(l^{\prime})$. Then, $u_{bl}$ = $u_{b}(l)$ \+ $u_{l}(b)$.. For a
matching $\mathbf{Z}$, let $m_{l,t}\in\mathcal{B}$ be the borrower assigned to
lender $l$ at time $t$, and $\mathbf{m}_{b,t}\subseteq\mathcal{L}$ be the set
of lenders that are assigned to borrower $b$ at time $t$, that is,

$\displaystyle m_{l}=b\Longleftrightarrow z_{bl}=1$
$\displaystyle\mathbf{m}_{b}:=\\{l\in\mathcal{L}\ |\ z_{bl}=1\\}$

considering the notations by dropping $t$ when we generalize the above for any
step $t$. In this parlance, a pair $(b,l)\in\mathcal{B}\times\mathcal{L}$ is a
blocking pair for $\mathbf{Z}$ if the following conditions C1 are satisfied:

  1. 1.

$z_{bl}=0$

  2. 2.

$z_{b^{\prime}l}=0$, $\forall b^{\prime}\neq b,b^{\prime}\in\mathcal{B}$ or
$u_{l}(b)$ $>$ $u_{l}(m_{l})$

  3. 3.

$\sum_{l\in\mathbf{m}_{b}}c_{l}$ $<q_{b}$ or $\exists$
$l^{\prime}\in\mathbf{m}_{b}$ such that $u_{b}(l)>u_{b}(l^{\prime})$.

A stable matching is defined based on the absence of blocking pairs as
follows: a matching $\mathbf{Z}$ is stable if it does not have any blocking
pairs. The stable matching model introduced by Gale-Shapley [44] finds a
matching using the deferred acceptance (DA) algorithm.However it does not
implicitly consider the notion of utility between the agents in that the
preference list is considered the ground truth for the assignments. Another
commonly employed algorithm is Gales’ top trading cycles (TTC) algorithm [43],
produces a matching that is Pareto-efficient but not necessarily stable. On
the other hand, as described in the previous section, The Gale-Shubik model
maximizes the total utility gained by the agents on either side of the market
based on the assumption that the utility can be exchanged between a borrower-
lender pair in the matching. This assignment model can be reduced to a linear
optimization problem but these do not maximize the total utility or agent
specific utility and suggests that the notion of stability and the objective
of utility are in general incompatible. To this end, we formulate our
objective of both stability respecting the preferences of the borrowers and
lenders while maximizing lender returns using a linear program formulation.
The Gale-Shapley notion of stable matching considering lender budget $q_{l}$
and borrower request $c_{b}$ for a pair $b-l$ can be characterized by the
following linear inequality as mentioned in [6]:

(4.1)
$c_{b}z_{bl}+c_{b}\sum_{l^{\prime}\succ_{b}l}z_{bl^{\prime}}+\sum_{b^{\prime}\succ_{l}b}q_{l}z_{b^{\prime}l}\geq
c_{b}$

The proof of the statement can be explained in the following way.

###### Theorem 1

Suppose that $\mathbf{Z}\in\\{0,1\\}^{|\mathcal{B}|\times|\mathcal{L}|}$ is a
matching. Then, it is stable if and only if constraint 4.1 is satisfied.

Proof: We prove the theorem by contraposition. If constraint 4.1 is violated
then it implies $\exists(b,l^{\prime})\in\mathcal{B}\times\mathcal{L};\
z_{bl}=0,\ \sum_{l^{\prime}\succ_{b}l}z_{bl^{\prime}}=0$, and
$\sum_{b^{\prime}\succ_{l}b}q_{l}z_{b^{\prime}l}<c_{b}$ which
$\Longleftrightarrow$ $\exists(b,l^{\prime})\in\mathcal{B}\times\mathcal{L}$;
$(b,l^{\prime})$ is a blocking pair for $\mathbf{z}$ following the assumptions
C1. This in turn implies Z is not stable.

We use this notation to arrive at a linear program that maximizes the utility
of the matching while minimizing the number of blocking pairs. Defining a
binary decision variable $\mathbf{w}$ := $(w_{b,l})$
$\in\\{0,1\\}^{|\mathcal{B}|\times|\mathcal{L}|}$, we use the following
constraint:

(4.2)
$c_{b}z_{bl}+c_{b}\sum_{l^{\prime}\succ_{b}l}z_{bl^{\prime}}+\sum_{b^{\prime}\succ_{l}b}q_{l}z_{b^{\prime}l}\geq
c_{b}(1-w_{bl})$

This characterization of the stability of matching markets can be understood
using the following observation: when $w$=0, this inequality is the same as
Equation 4.1, and so $w_{bl}$ denotes that $(b,l)$ is a blocking pair and so
the number of blocking pairs is given by $\sum_{b}\sum_{l}w_{bl}$. The
objective is to maximize the utility and minimize the number of blocking pairs
at the same time. The matching objective keeping the above constraints can be
formulated as MQ1:

(4.3) $\begin{array}[]{ll@{}ll}\text{maximize
}&\lambda_{1}\sum_{b\in\mathcal{B}}\sum_{l\in\mathcal{L}}u_{l}(b)x_{bl}-\lambda_{2}\sum_{b\in\mathcal{B}}\sum_{l\in\mathcal{L}}w_{bl}\end{array}$
$\begin{array}[]{ll@{}ll}\text{subject \ to}&\sum_{b\in\mathcal{B}}x_{bl}\leq
1\ \ \ \ (\forall l\in\mathcal{L})\\\ &\sum_{l\in\mathcal{L}}x_{bl}q_{l}\geq
c_{b}\ \ \ \ \ (\forall b\in\mathcal{B})\\\
&c_{b}x_{bl}+c_{b}\sum_{l^{\prime}\succ_{b}l}x_{bl^{\prime}}+\sum_{b^{\prime}\succ_{l}b}q_{l}x_{b^{\prime}l}\\\
&\geq c_{b}(1-w_{bl})(\forall l\in\mathcal{L},\forall b\in\mathcal{B})\\\
&x_{bl}\in\\{0,1\\}\ \ \ \ (\forall b\in\mathcal{B},\forall
l\in\mathcal{L})\\\ &w_{bl}\in\\{0,1\\}\ \ \ \ (\forall
b\in\mathcal{B},\forall l\in\mathcal{L})\end{array}$

We denote the set of constraints above as C2. Briefly these constraints
satisfy the following: (1) the lenders can only be matched to one borrower,
(2) the number of blocking pairs (denoted by $w_{bl}$) should be minimized in
accordance with the original stable matching constraints [39], and the
borrower’s requested amount must exceed the sum of investments from matched
lenders. This is in addition to the constraint 4.1 which minimizes the number
of blocking pairs while maximizing the utility. Note above that we optimize
for the lender utility in Equation 4.3 but we will come back to this setting
when we evaluate our matching objective and which also constitutes the need
for our IP formulation instead of the traditional Gale-Shapley agent optimal
algorithm.

###  4.2 Utility constraints

Reasons for lender preferences over borrowers could arise from the return on
investment (ROI) which could be calculated in a myriad ways using a lot of
other factors 333http://blog.lendingrobot.com/research/calculating-financial-
returns-in-peer-lending/. For the borrower, the main reason to prefer one
lender over another is the past reputation of the lender (since network
effects can significantly accelerate the funding [25]) as well as the interest
matches (especially in VC funding, the investor liquidation preferences can
play a role in startup preferences). As for the lender case, we sample
$u_{b}(l)$ from a uniform distribution. These utilities have been optimized
for lender returns in settings of recommendation systems [19]. In our settings
for preference elicitation, the matching objective function with constraints
as defined in the previous section depends on the preferences that are set by
agents on both sides at each step of the matching. We consider the utilities
$\mathbf{u}_{b}=\\{u_{b}(l_{1}),u_{b}(l_{2})...\\}$, $l_{i}\in\mathcal{L}$ and
$\mathbf{u}_{l}=\\{u_{l}(b_{1}),u_{l}(b_{2})...\\}$, $b_{i}\in\mathcal{B}$
that denote the vector of values for each agent $l$ or $b$ about its
preferences of agents on the other side of the market. And as stated before,
the ordering depends on the value that the agents estimate prior to matching.
There are two ways we use these utilities in our market design:

  * •

Lender utilities \- Preferences from each lender are elicited using their
utility functions. So, each lender $l$ ranks the borrowers using their
utilities set at the start of the matching. However, in the sequential
decision time step, each lender gets to revise its utilities based on the
rewards $X_{l,t}(b)$ it obtains from the matching at a particular round. In
our setting, the lender utilities at time $t$ for $l$ is adjusted on whether a
lender is matched to borrower $b$: $u_{l,t}(b)=u_{l,t-1}(b)+X_{l,t}(b)$ if
$m_{l}=b$ at time step $t$ for matching $z$. We will discuss the choices of
$X$ in Section 5 to ensure calibration of the utility values. In our work we
consider that $u_{l}(b)$ depends on two factors: lender budget $q_{l}$ and
borrower rate $\eta_{b}$/

  * •

Borrower utilities \- Similar to the lender, each borrower $b$ ranks the
borrowers using their utilities set at the start of the matching. However,
unlike the lender, we assume that the borrower utilities are fixed over time.

##  5 Sequential decision making

One important point to recall is that the agents on each side are not aware of
the preferences of each other irrespective of which side they belong to, which
is why the case for competition arises more prominently. In hindsight, such
preferences are not globally known since user preferences for each other
change over time, so the estimated utilities also change over time . In order
to arrive at a preferred matching faster, we operationalize the matching
platform with sequential decision making in the form of multi-armed bandits
with a centralized matching platform. This notion of centralized matching
markets has been studied before in [32, 7]. In the framework of sequential
decision making, we allow lenders to submit their preferences over multiple
time steps and subsequently the matching happens in these steps or rounds. The
lender receives a reward at each step determined by which borrower it gets
matched to. From the lender’s point of decision making, the uncertainty comes
from the absence of knowledge of the borrower preferences (or utilities) to
the lenders. This is a bandit setting [21] where at each round, the platform
provides a pseudo-reward to the lender based on the borrower it is matched to
and allows the lender to revise its preference rankings for the next round.
The goal of each lender is to get matched to its most preferred lender at each
round and this happens when the gap between the lender utility and the rewards
narrows.

Algorithm 1 Matching between borrowers and lenders (GS-UCB)

Input: $\mathcal{B}$, $\mathcal{L}$, $\mathbf{u}_{l}$, $\mathbf{u}_{b}$, $T$.
Output: Matching dictionaries $\mathcal{M}_{\mathcal{B}}$,
$\mathcal{M}_{\mathcal{L}}$

1:$cu_{l}(b)$ $\leftarrow$ $\infty$ ($\forall b\in\mathcal{B},\forall
l\in\mathcal{L}$)

2:$T_{b,l}(0)$ $\leftarrow$ 0 ($\forall b\in\mathcal{B},\forall
l\in\mathcal{L}$)

3:for t = 1, 2, $\ldots$ T do

4: $\mathcal{M}_{\mathcal{B}}$, $\mathcal{M}_{\mathcal{L}}$ $\leftarrow$
Matching MQ1 using $cu_{l}$ and $u_{b}$ ($\forall b\in\mathcal{B},\forall
l\in\mathcal{L}$)

5: for l $\in$ $\mathcal{L}$ do

6: $m_{l,t}$ $\leftarrow$ $\mathcal{M}_{\mathcal{L}}(l)$ $\triangleright$
matched borrower

7: if $m_{t}(l)$ is not empty then

8: $r$ $\leftarrow$ $X_{l,t}(m_{l,t})$ $\triangleright$ lender reward

9: Update $\hat{\mu}_{l}(m_{l,t})$ using $r$ in Equation 5.4

10: $T_{m_{l,t},l}(t)$ $\leftarrow$ $T_{m_{l,t},l}(t-1)$ \+ 1

11: end if

12: for b $\in\mathcal{B}$ do

13: $cu_{l}(b)$ $\leftarrow$ $\hat{\mu}_{l}(b)$ \+ $\sqrt{\frac{3\ \mbox{log}\
t}{2\ T_{b,l}(t)}}$

14: end for

15: end for

16:end for

17:return $\mathcal{M}_{\mathcal{B}}$, $\mathcal{M}_{\mathcal{L}}$

###  5.1 Matching with UCB (GS-UCB)

In this setting we assume that the horizon T is not known to the agents and is
much larger than $|\mathcal{B}|$ and $|\mathcal{L}|$, since we assume the
matching happens over a long period of time. In what follows, we explain how
the reward distributions for each lender are calculated and which lays the
path for the exploration of the arms (here the borrowers) by the lenders at
each round. Before describing the desiderata for the reward structure, we
recall that for a lender $l$, the set of arms or borrowers $b\in\mathcal{B}$
are associated with random variables $X_{l,t}(b)$, $t\geq 1$ with bounded
support on [0, 1]. The variable $X_{l,t}(b)$ indicates the random outcome of
the borrower $b$ at time $t$ such that $m_{t}(l)=b$. These set of random
variables $\\{X_{l,t}(b)\ |\ t\geq 1\\}$ associated with lender $l$ are
independent and identically distributed according to some unknown distribution
with expectation $u_{b}(l)$, $\forall b\in\mathcal{B}$. The empirical mean for
the lender $l$ for the set of borrowers is denoted by $\hat{\mu}_{l}(b)$. We
consider two assumptions similar to the work done in [17] on the reward
structure that allows us to guarantee bounds on the lender $l$’s regret of the
matching over time:

  * •

Monotonicity: The expected reward for a lender $l$ from a set of borrowers is
monotonically non decreasing with respect to the expectation vector, i.e. if
$\forall b\in\mathcal{B}$, $u_{b}(l)\leq u_{b^{\prime}}(l)$, then it is
guaranteed that $\hat{\mu}_{l}(b)$ $\leq\hat{\mu}_{l}(b^{\prime})$.

  * •

Bounded smoothness: This property requires that for any two expectation
vectors $u_{b}(l^{\prime})$ and $u_{b}^{\prime}(l)$, such that
$max_{b\in\mathcal{B}}|u_{b}(l)-u_{b}(l^{\prime})|\ \leq\Lambda$ we should
have $|\hat{\mu}_{l}(b)-\hat{\mu}_{l}(b^{\prime})|$ $\leq f(\Lambda)$.

Now, we describe the matching algorithm utilizing a popularly technique in the
set of bandit based algorithms known as the Upper Confidence Bound (UCB) [30].
At each time step in Algorithm 1, the platform matches lender $l$ with
borrower $m_{l}$ upon which $l$ is deemed to be able to pull the arm
successfully and gets to know the reward $X_{l,t}(b)$. Lender $l$ updates
their empirical mean $\hat{\mu}_{l}(m_{l})$ through the following equation:

(5.4)
$\hat{\mu}_{l}(b)=u_{l}(b)+\frac{1}{1+T_{b,l}(t)}\Big{[}\sum_{s=1}^{t}\mathbf{1}\\{m_{s}(l)==b\\}X_{l,s}(b)\Big{]}$

where $T_{b,l}(t)$ = $\sum_{s=1}^{t}\mathbf{1}\\{m_{l}(s)==b\\}$ is the number
of times borrower $b$ was matched to lender $l$ till time $t$. In Algorithm 1,
$\mathcal{M}_{l}$ denotes the storage structure mapping each borrower to a
lender $l$ and similarly and $\mathcal{M}_{b}$ denotes the set of lenders
matched to a borrower which is output at each time step by MQ1. We utilize the
Upper Confidence Bound (UCB) design [30] where at each time step $t$ the
lenders compute the upper confidence bound for each borrower as follows:

(5.5) $cu_{l}(b)=\begin{cases}\infty\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ ,\ T_{b,l}(t)=0\\\ \hat{\mu}_{l}(b)+\sqrt{\frac{3\ \mbox{log}\
t}{2\ T_{b,l}(t)}}\ \ \ \ \ \ \ \ ,\ otherwise\\\ \end{cases}$

Each lender $l$ ranks the arms $b$ according to $cu_{l}(b)$ and sends the new
utilities $\mu_{l}(b)$ to the platform while the borrower preferences remain
unchanged. The important point to note is that at each step from $t\geq 1$,
the objective utility to maximize for the lender is $\mu_{l}(b)$, however the
preference ordering in the set of constraints C2 is done using
$\mathbf{cu}_{l}$.

Algorithm 2 Matching between borrowers and lenders (GS-BLEMET)

Input: $\mathcal{B}_{unm}$, $\mathcal{L}_{unm}$, $\mathbf{c}$,
$\mathbf{u}_{l}$, $\mathbf{u}_{b}$, $\mathbf{q}$.
Output: Matching dictionaries $\mathcal{M}_{\mathcal{B}}$,
$\mathcal{M}_{\mathcal{L}}$

1:$cu_{l}(b)$ $\leftarrow$ $\infty$ ($\forall b\in\mathcal{B}_{unm},\forall
l\in\mathcal{L}_{unm}$)

2:$cl_{l}(b)$ $\leftarrow$ $-\infty$ ($\forall b\in\mathcal{B}_{unm},\forall
l\in\mathcal{L}_{unm}$)

3:$T_{b,l}(0)$ $\leftarrow$ 0 ($\forall b\in\mathcal{B}_{unm},\forall
l\in\mathcal{L}_{unm}$)

4:$\mathcal{M^{\prime}}_{\mathcal{B}}$ $\leftarrow$ $\\{\\}$,
$\mathcal{M^{\prime}}_{\mathcal{L}}$ $\leftarrow$ $\\{\\}$ ($\forall
b\in\mathcal{B}_{unm},\forall l\in\mathcal{L}_{unm}$)

5:for t = 1, 2, …T do

6: $\mathcal{M}_{\mathcal{B}}$, $\mathcal{M}_{\mathcal{L}}$ $\leftarrow$
Matching MQ1 using $cu_{l}$ and $u_{b}$ ($\forall
b\in\mathcal{B}_{unm},\forall l\in\mathcal{L}_{unm}$)

7: for b $\in$ $\mathcal{B}_{unm}$ do

8: $\triangleright$ Find all lenders matched to borrower $b$

9: $\mathbf{m}_{b}$ $\leftarrow$ $\mathcal{M}_{\mathcal{B}}$[$b$]

10: for l $\in$ $\mathbf{m}_{b}$ do

11: $\triangleright$ If $b$ is currently $l$’s ”most” preferred borrower

12: if $cl_{l}(b)$ $>$ $max\ \Theta_{l}(\mathcal{B}_{unm}\setminus b)$ then

13: $\triangleright$ If $l$ is most preferred among other lenders for $b$

14: if $cl_{l}(b)$ $>$ $max\ \Upsilon_{b}(p_{n}\setminus l)$ then

15:
$\mathcal{M^{\prime}}_{\mathcal{B}}(b)=\mathcal{M^{\prime}}_{\mathcal{B}}(b)\cup
l$, $\mathcal{M^{\prime}}_{\mathcal{L}}(l)=b$

16: $\mathcal{L}_{unm}$ $\leftarrow$ $\mathcal{L}_{unm}$ $\setminus$ $l$

17: $c_{b}$ $\leftarrow$ $c_{b}$ \- $q_{l}$

18: end if

19: else

20: $r$ $\leftarrow$ $X_{l,t}(b)$ $\triangleright$ lender reward

21: Update $\hat{\mu}_{l,t}(b)$ using $r$ in Equation 5.4

22: $cu_{l,t}(b)$ $\leftarrow$ $\hat{\mu}_{l,t}(b)$ \+ $\sqrt{\frac{3\
\mbox{log}\ t}{2\ T_{b,l}(t-1)}}$

23: $cl_{l,t}(b)$ $\leftarrow$ $\hat{\mu}_{l,t}(b)$ \- $\sqrt{\frac{3\
\mbox{log}\ t}{2\ T_{b,l}(t-1)}}$

24: Update $\Upsilon_{b}(l)$ and $\Theta_{l}(b)$ using $cu_{l,t}(b)$ and
$cl_{l,t}(b)$ respectively

25: $T_{b,l}(t)$ $\leftarrow$ $T_{b,l}(t-1)$ \+ 1

26: end if

27: end for

28: end for

29: for b $\in$ $\mathcal{B}_{unm}$ do

30: if $C$[$b$] $\leq$ 0 then

31: $\mathcal{B}_{unm}$ $\leftarrow$ $\mathcal{B}_{unm}$ $\setminus$ $b$

32: end if

33: end for

34: Broadcast $\mathcal{B}_{unm}$ to the lenders $\mathcal{L}_{unm}$

35: if $\mathcal{L}_{unm}$ is empty or $\mathcal{B}_{unm}$ is empty then

36: break;

37: end if

38:end for

39:return $\mathcal{M^{\prime}}_{\mathcal{B}}$,
$\mathcal{M^{\prime}}_{\mathcal{L}}$

###  5.2 Matching with Early Termination (GS-BLEMET)

One of the drawbacks of the baseline UCB algorithm is that in the absence of
networked environments or absence of side observations as is the case with
previous studies [10, 33], the lenders are not able to view the preferences
for lenders also competing for that borrower. This issue is also aggravated
since we do not consider strategic agents in our settings and the preferences
set by the lenders at each time step is bereft of external information about
their standing among other lenders for a specific borrower. That is, if the
lender $l$’s estiamte of the empirical upper bound $cu_{l}(b)$ of a borrower
arm $b$ is already very high compared to the other lenders, then it is better
to match $b$ to $l$, update $b$’s remaining amount to bid on and remove the
lender from the further rounds, so that the other lenders can revise their
estimates of the borrowers. This is reminiscent of the successive elimination
algorithm used in the bandit settings [23]. To that end, we devise an
algorithm for Borrower and LEnder Matching with Early Termination (BLEMET)
described in Algorithm 2. We define two symbols: $\Upsilon_{b,t}$ =
$\\{cu_{l}(b)\\}$ $\forall l\in\mathcal{L}$, which stores the UCB of all
lenders $l$ with respect to the borrower $b$ at step $t$, and $\Theta_{l}$ =
$\\{cu_{l}(b)\\}$ $\forall b\in\mathcal{B}$ which stores the UCB of all
borrowers $b$ with respect to the lender $l$’s estimates. The main steps in
this design of the algorithm can be summarized in these three steps (note that
in our centralized platform, the matching and decisions of termination are
driven solely by the platform/matching algorithm itself and the agents drive
this decision by adjusting their utilities through their preferences over time
unlike a decentralized distributed setting):

  1. 1.

The goal is to match each lender to a borrower as soon as a criterion is met.
To this end, we keep a list of unmatched borrowers and lenders at each time
point as per our definitions of matching in $\mathcal{L}_{unm}$ and
$\mathcal{B}_{unm}$ (these sets are initialized as $\mathcal{L}$ and
$\mathcal{B}$ respectively). At each time step, we find the matching
$\mathcal{M}_{\mathcal{B}_{unm},\mathcal{L}_{unm}}$ using the optimization
objective described in Equation 4.3 to find the map of borrowers matched to
lenders in Step 6. We follow the same initialization of $cu_{b}$ defined in
Equation 5.5 and additionally, we define $cl_{b}$ except we subtract the term
in the square root in Equation 5.5 from $\hat{\mu}_{l}(b)$.

  2. 2.

For each borrower $b$ $\in\mathcal{B}_{unm}$, we extract the set of lenders
$p_{b}$ who are matched to $b$ in the current time step. Lines 11-14 define
the two criteria that we consider for early termination - if $l$’s estimate of
LCB for $b$ is higher than the UCB of all other borrowers unmatched so far
defined in Line 12 and if $l$’s LCB is higher than the UCB of all other
lenders contesting for $b$ defined in Line 14. When both of these conditions
are met, the borrower $b$ is set to be matched to the lender $l$ and is
removed from further iterations and we update $\mathcal{L}_{unm}$ and borrower
$b$’s remaining requested amount $c_{b}$. If either of the conditions are not
met, then we just update the UCB and LCB estimates of the lenders $p_{b}$ for
the borrower $b$, as shown in Lines 20-24.

  3. 3.

The final step also includes checking whether a borrower has its request
already met by the allocations so far after early termination. To this end, we
check whether the borrower’s remaining request $c_{b}$ is less than 0, and in
that case, we remove borrower $b$ from further iterations of the game.
Finally, we broadcast the remaining borrowers to the lender. Line 35 is
important in this algorithm in that the termination depends not just on the
horizon T but on the UCb updates as well.

We continue these three steps for all the iterations of the game until we
reach the maximum iterations $T$ or all the borrowers and lenders have been
matched, whichever happens earlier.

##  6 Equitable allocations

So far, we have presented a situation that takes into account the best
interests of both the borrowers and the lenders through their utility
functions. However, as mentioned previously, there are several factors hat
influence a lender’s decision like the probability of a borrower listing
getting fully funded, the probability of the lender getting matched, the
interest rate [47, 11] which are uncertain, but apart from that there can be
bias to the choices themselves - like preference for new listings, preference
for specific countries [9], preference for creditworthy borrowers, popularity
bias as seen in recommendation systems [1]. The added constraint of early
termination in BLEMET can cause some borrowers to lose out on the bidding and
to mitigate these issues, we add the following term that captures the worst
case allocation to the borrowers. We want to minimize the maximum $c_{b,t}$
over time (note that $c_{b,t}$ is adjusted at each time step $t$ in GS-BLEMET)
so as to ensure equitable allocations. We capture that by minimizing the
following component in addition to the objectives optimized so fat:
$\kappa(t)=max_{b\in\mathcal{B}}\ c_{b,t}*e^{\omega\frac{t}{T}}$, where
$\omega$ is a hyper parameter and $t$ is the time step of the matching.
Following this, we define the matching objective M2 as:

(6.6) $\begin{array}[]{ll@{}ll}\text{maximize
}&\lambda_{1}\sum_{b\in\mathcal{B}}\sum_{l\in\mathcal{L}}u_{bl}z_{bl}\\\
-\lambda_{2}\sum_{b\in\mathcal{B}}\sum_{l\in\mathcal{L}}w_{bl}\\\
-\lambda_{3}\ \kappa(t)\end{array}$

$\begin{array}[]{ll@{}ll}\text{subject \ \ to}&\mathbf{C2}\end{array}$

##  7 Experiments

###  7.1 Simulation Settings

To understand how the settings described in Section 5 compare in terms of the
regret dynamics, we simulate our findings with agents with utilities and
rewards generated in a stochastic environment. Our code is fully open sourced
and can be accessed 444https://bit.ly/3iylv8X. We consider 20 borrowers and 60
lenders as the agents on two sides of the market. To assign a loan request
budget for the borrowers and an investment budget for the lenders, we simulate
using the following rule. We set the configurations of the simulations in the
following way:

  * •

Loans and Budgets: We uniformly sample loans values $\mathbf{c}$ in the range
of 10 and 50 for the borrowers. We fix the lender investment budgets
$\mathbf{q}$ by selecting a value uniformly in the range of 1 and 30 such that
the configuration of the borrower and lender budgets satisfy the following
criterion: the sum of the lender amounts exceed the sum of the borrower
requests. This configuration setting ensures that there would be a valid
matching that could be obtained using the optimization objective satisfying
the resource constraints of the lenders and the borrowers. However, this
constraint could be relaxed even if we add the assumption that not all
borrowers need to be matched in every time step.

  * •

Utilities: We randomly sample borrower rates $\boldsymbol{\eta}$ for each $b$
$\in\mathcal{B}$ from a uniform distribution in the range (0, 1) and the
borrower utilities for each lender $u_{b}(l)$ are sampled from a uniform
distribution in the range (0, 1). Following this, the lender utilities
$u_{l}(b)$ are calculated as $\eta_{b}*q(l)$. We the normalize the lender
utilities to calibrate them in the range of the borrower utilities.

  * •

Rewards: As mentioned before, for each borrower-lender b-l pair, we sample the
rewards from a 1-subgaussian distribution with mean $u_{b}(l)$. One thing to
note that these rewards $X_{l,t}(b)$ for a lender $l$ from $b$ at $t$ which
depends on $u_{b}(l)$ would not necessarily be the same for each $t$ and this
is where stochasticity comes into play. That is to say, the reward for a
lender $l$ when matched to a borrower $b$ at time step $t$ could be different
time step $t^{\prime}$ even if the lender $l$ was matched to $b$ both at $t$
and $t^{\prime}$.

Before moving to the evaluation settings and the results, we discuss the
hyperparameter values, especially $\lambda_{1},\lambda_{2}$ and $\lambda_{3}$.
For the setting without the fairness component in the objective, we set the
$\lambda_{1},\lambda_{2}$ to 0.5 each keeping them in equal proportions and
for the objective including the fairness constraint, we set $\lambda_{1}$ to
0.5 and grid search for $\lambda_{2}$ and $\lambda_{3}$ such
$\lambda_{2}+\lambda_{2}$ = 0.5. One additional point to note is that since we
consider early termination in the algorithm GS-BLEMET, when a lender $l$ is
removed from the simulation instance at time step $t$, we consider the regret
constant for all time steps after $t$ for lender $l$.

To simulate the matching, we run the different settings for 10000 steps and
simulate each setting for 50 times. These 50 simulations are run keeping the
initial utilities $\mathbf{u_{b}}$ and $\mathbf{u_{l}}$ unchanged as well as
the hyper-parameters for the algorithm constant. The only stochastic
components come from the uncertainty about the rewards obtained over time
which control the learning mechanism.

###  7.2 Evaluation

To evaluate the quality of the lender assigned borrowers, we compute the
following cumulative regret metric for each lender at each time step $t$:
$t*u_{l}(b_{opt})-\sum_{i=1}^{t}E[\ \mathcal{R}(u_{l}(b_{alg}))]$ where $E[.]$
denotes expect $b_{alg}$ is the matched borrower for lender $l$ at time $t$
returned in Algorithm 1 while $b_{opt}$ is computed using the following
optimization:

(7.7) $\begin{array}[]{ll@{}ll}\text{maximize
}&\lambda_{1}\sum_{b\in\mathcal{B}}\sum_{l\in\mathcal{L}}u_{b,l}z_{bl}-\lambda_{2}\sum_{b\in\mathcal{B}}\sum_{l\in\mathcal{L}}w_{bl}\end{array}$
$\begin{array}[]{ll@{}ll}\text{subject \ to}&\textbf{C1}\end{array}$

Note we optimize the sum of the borrower and lender utilities as in hindsight,
the lender would have adjusted its ranking based on borrower preferences had
it have access to that information. However, we do not note that this setting
we which call the optimal setting is not guaranteed to produce the best
matching in terms of the utility that the lender receives since this is the
gap we have for some lenders attributed to the difference between the matching
objective and the lender returns.

###  7.3 Results

We start by observing the results from the GS-UCB algorithm in Algorithm 1,
and we observe three kinds of dynamics in the lender regrets:

Figure 1: Cumulative expected lender regret over time simulated over 50 runs.

for lenders 53 and 37 shown in Figure 1, we find that the regret either comes
to near equilibrium or moves slowly towards saturation. However, for lenders
where we find the regret becomes stationary like lender 37 after certain time
steps, the learning rate towards better choices can be slower than other cases
as the regret shown for lender 53. We find that lenders like lender 50 are not
able to learn as best as the optimal solution in that we see the regret is
non-decreasing over the course of the simulation. However, what is interesting
to see is that for lender 7, we see the regret is non-increasing, meaning that
the lender utilities of lender 7 for all time steps are at least as good as
the one returned by the optimal solution. So in the presence of complicated
functions f(.) characterizing the lender returns, optimizing the lender and
borrower utilities as the matching objective as done for the optimal solution
might not always yield the best lender returns.

Figure 2: Heatmaps showing the lender matchings over the time steps from 50
simulations.

When we look at the heatmaps in Figure 2 where the grids denote the count of
the number of times the lender was matched to borrower arm at each time step
over 50 simulation runs. When considering the regret plots in Figure 1 with
these heatmaps, we find that despite the stochasticity of the rewards, the
lenders 53 and 37 start getting matched to the same borrower at the time when
their regret starts to saturate. For lender 50, we find that the lender is not
able to learn the best arm over the horizon which also explains its increasing
regret over time. Note that the increasing regret dynamic can be explained by
two situations: one when the lender has learnt the wrong optimal arm and when
the lender is not able to learn any one arm over time steps.

We next look at the comparison of the 3 settings: GS-UCB, GS-BLEMET, GS-
BLEMET-FAIR described in Section 5 to understand how the dynamics of
cumulative regret compare among these methods. We want to outright mention
that although the algorithm GS-BLEMET uses the UCB algorithm for deciding the
termination thresholds, the cumulative regret of some lenders would be
constant after they have been terminated from the matching although the
matching for other lenders continue.

Figure 3: Cumulative expected lender regret over time simulated over 50 runs.

From Figure 3, we find that the lender regrets can be categorize into three
groups. First, represented in the regret plots for lenders 16 and 38, we find
the GS-BLEMET regret is as good as the GS-UCB regret over all time steps and
also better for lender 38. However, in these cases we find that the fairness
constraint using the maximum remaining amount for a borrower to penalize the
objective in GS-BLEMET-FAIR hurts the regret of these lenders compared to the
other algorithms. On the other hand, we find that for lenders 7 and 8, the
cumulative regret is better for GS-BLEMET-FAIR than GS-UCB, both when the
cumulative regrest either increase or decrease over time. These aggregated
plots attest to the observation that there is not one rule that the dynamics
of regret follows especially as the matching objective and constraints include
a lot of factors into consideration. Recall that the main objective for GS-
BLEMET-FAIR is to improve overall borrower regrets for the worst performing
borrower, despite this we observe that the lender regrets although impacted
for some lenders, are not worse according to this algorithm for every lender.

Figure 4: Cumulative expected lender regret over time simulated over 50 runs.

However, when we compare the sum of the lender regrets for both GS-UCB and the
GS-BLEMET algorithms, we do find that the early termination criteria helps in
lowering the cumulative regret over time as shown in Figure 4.

##  8 Conclusions and Future work

We consider a case of a centralized matching platform which requests proposals
from borrowers about their preferences over the lenders or the agents through
their personal rankings of the lenders. Then the platform decides the matching
by allowing the lenders to interact with the platform over multiple time steps
by either accepting or rejecting the assigned borrower at a time step. From a
lender perspective, this schema thus allows them to get matched without having
the information of the actual returns while allowing them certain flexibility
to exploit their options. The goal of this paper has been to lay out some
ideas in which centralized peer lending platforms can be abstracted from a
matching market perspective and how bandits could play a role in such
mechanism design. These matching markets allow for more privacy as well as
ensuring equitable outcomes and in our situation can be achieved by designing
proper utility functions and rewards for the agents. Similarly, in future one
could design decision making in which lenders can elicit information about
their peer choices as well as networks have been known to aid funding
situations [25] . In this paper, we did not consider externalities in the
matching especially, when information among agents over time can change the
dynamics of matching. Such effects of peer preferences[8] or externalities[37,
33] have been known to introduce substitutes in the markets. One of the tenets
of crowdfunding platforms is the probability of the borrower listing getting
fully funded and that additionally constitutes the uncertain elements at the
start of the matching. In our settings, this constraint was not violated as we
included it as part of our constraints explicitly. However, in real world,
many projects will not reach their reserve prices for the requested loans and
such cases need to be handled explicitly.

## References

  * [1] H. Abdollahpouri, R. Burke, and B. Mobasher, Managing popularity bias in recommender systems with personalized re-ranking, arXiv preprint arXiv:1901.07555, (2019).
  * [2] S. Agrawal and N. R. Devanur, Bandits with concave rewards and convex knapsacks, in Proceedings of the fifteenth ACM conference on Economics and computation, 2014, pp. 989–1006.
  * [3] M. Akbarpour, S. Li, and S. O. Gharan, Dynamic matching market design, arXiv preprint arXiv:1402.3643, (2014).
  * [4] M. Babaioff, S. Dughmi, R. Kleinberg, and A. Slivkins, Dynamic pricing with limited supply, 2015.
  * [5] A. Badanidiyuru, R. Kleinberg, and A. Slivkins, Bandits with knapsacks, in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, 2013, pp. 207–216.
  * [6] M. Baïou and M. Balinski, The stable admissions polytope, Mathematical programming, 87 (2000), pp. 427–439.
  * [7] I. Bistritz, T. Baharav, A. Leshem, and N. Bambos, My fair bandit: Distributed learning of max-min fairness with multi-player bandits, in International Conference on Machine Learning, PMLR, 2020, pp. 930–940.
  * [8] E. Bodine-Baron, C. Lee, A. Chong, B. Hassibi, and A. Wierman, Peer effects and stability in matching markets, in International Symposium on Algorithmic Game Theory, Springer, 2011, pp. 117–129.
  * [9] G. Burtch, A. Ghose, and S. Wattal, Cultural differences and geography as determinants of online prosocial lending, Mis Quarterly, 38 (2014), pp. 773–794.
  * [10] S. Caron, B. Kveton, M. Lelarge, and S. Bhagat, Leveraging side observations in stochastic bandits, arXiv preprint arXiv:1210.4839, (2012).
  * [11] S. Ceyhan, X. Shi, and J. Leskovec, Dynamics of bidding in a p2p lending service: effects of herding and predicting loan success, in Proceedings of the 20th international conference on World wide web, 2011, pp. 547–556.
  * [12] K.-M. Chen, Y.-W. Hsieh, and M.-J. Lin, Prediction and congestion in two-sided markets: Economist versus machine matchmakers, Available at SSRN 3318778, (2019).
  * [13] , Reducing recommendation inequality via two-sided matching: a field experiment of online dating, Available at SSRN, (2020).
  * [14] N. Chen and A. Ghosh, A market clearing solution for social lending, in IJCAI, vol. 11, 2011, pp. 152–157.
  * [15] N. Chen, A. Ghosh, and N. Lambert, Social lending, in Proceedings of the 10th ACM conference on Electronic Commerce, 2009, pp. 335–344.
  * [16] N. Chen, A. Ghosh, and N. S. Lambert, Auctions for social lending: A theoretical analysis, Games and Economic Behavior, 86 (2014), pp. 367–391.
  * [17] W. Chen, Y. Wang, and Y. Yuan, Combinatorial multi-armed bandit: General framework and applications, in International Conference on Machine Learning, PMLR, 2013, pp. 151–159.
  * [18] A. Chiesa, S. Micali, and Z. A. Zhu, Bridging utility maximization and regret minimization, arXiv preprint arXiv:1403.6394, (2014).
  * [19] J. Choo, C. Lee, D. Lee, H. Zha, and H. Park, Understanding and promoting micro-finance activities in kiva. org, in Proceedings of the 7th ACM international conference on Web search and data mining, 2014, pp. 583–592.
  * [20] R. Combes, C. Jiang, and R. Srikant, Bandits with budgets: Regret lower bounds and optimal algorithms, ACM SIGMETRICS Performance Evaluation Review, 43 (2015), pp. 245–257.
  * [21] S. Das and E. Kamenica, Two-sided bandits and the dating market., in IJCAI, vol. 5, 2005, p. 19.
  * [22] E. Emamjomeh-Zadeh, Y. A. Gonczarowski, and D. Kempe, The complexity of interactively learning a stable matching by trial and error, arXiv preprint arXiv:2002.07363, (2020).
  * [23] E. Even-Dar, S. Mannor, Y. Mansour, and S. Mahadevan, Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems., Journal of machine learning research, 7 (2006).
  * [24] R. Gonen and E. Pavlov, An incentive-compatible multi-armed bandit mechanism, in Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, 2007, pp. 362–363.
  * [25] E.-Á. Horvát, J. Uparna, and B. Uzzi, Network vs market relations: The effect of friends in crowdfunding, in Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015, 2015, pp. 226–233.
  * [26] L. Jain and K. Jamieson, Firing bandits: Optimizing crowdfunding, in International Conference on Machine Learning, PMLR, 2018, pp. 2206–2214.
  * [27] R. Johari, V. Kamble, and Y. Kanoria, Matching while learning, Operations Research, (2021).
  * [28] M. Joseph, M. Kearns, J. Morgenstern, and A. Roth, Fairness in learning: Classic and contextual bandits, arXiv preprint arXiv:1605.07139, (2016).
  * [29] M. Kumar and S. I. Feldman, Internet auctions., in USENIX Workshop on Electronic Commerce, vol. 3, 1998, pp. 49–60.
  * [30] T. L. Lai and H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in applied mathematics, 6 (1985), pp. 4–22.
  * [31] L. T. Liu, S. Dean, E. Rolf, M. Simchowitz, and M. Hardt, Delayed impact of fair machine learning, arXiv preprint arXiv:1803.04383, (2018).
  * [32] L. T. Liu, H. Mania, and M. Jordan, Competing bandits in matching markets, in International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 1618–1628.
  * [33] S. Mannor and O. Shamir, From bandits to experts: On the value of side-observations, arXiv preprint arXiv:1106.2436, (2011).
  * [34] M. Mladenov, E. Creager, O. Ben-Porat, K. Swersky, R. Zemel, and C. Boutilier, Optimizing long-term social welfare in recommender systems: A constrained matching approach, in International Conference on Machine Learning, PMLR, 2020, pp. 6987–6998.
  * [35] H. Nguyen, T. Nguyen, and A. Teytelboym, Stability in matching markets with complex constraints, Management Science, (2021).
  * [36] G. K. Patro, A. Biswas, N. Ganguly, K. P. Gummadi, and A. Chakraborty, Fairrec: Two-sided fairness for personalized recommendations in two-sided platforms, in Proceedings of The Web Conference 2020, 2020, pp. 1194–1204.
  * [37] M. Pycia and M. B. Yenmez, Matching with externalities, (2019).
  * [38] B. Rastegari, P. Goldberg, and D. Manlove, Preference elicitation in matching markets via interviews: A study of offline benchmarks, arXiv preprint arXiv:1602.04792, (2016).
  * [39] A. E. Roth, U. G. Rothblum, and J. H. Vande Vate, Stable matchings, optimal assignments, and linear programming, Mathematics of operations research, 18 (1993), pp. 803–828.
  * [40] A. Sankararaman, S. Basu, and K. A. Sankararaman, Dominate or delete: Decentralized competing bandits with uniform valuation, arXiv preprint arXiv:2006.15166, (2020).
  * [41] S. Sarkar and H. Alvari, Mitigating bias in online microfinance platforms: A case study on kiva. org, ECML PKDD SoGood, (2020).
  * [42] S. Schmit and C. Riquelme, Human interaction with recommendation systems, in International Conference on Artificial Intelligence and Statistics, PMLR, 2018, pp. 862–870.
  * [43] L. Shapley and H. Scarf, On cores and indivisibility, Journal of mathematical economics, 1 (1974), pp. 23–37.
  * [44] L. S. Shapley and M. Shubik, The assignment game i: The core, International Journal of game theory, 1 (1971), pp. 111–130.
  * [45] K. Tu, B. Ribeiro, D. Jensen, D. Towsley, B. Liu, H. Jiang, and X. Wang, Online dating recommendations: matching markets and learning preferences, in Proceedings of the 23rd international conference on world wide web, 2014, pp. 787–792.
  * [46] Z. Wei and M. Lin, Market mechanisms in online peer-to-peer lending, Management Science, 63 (2017), pp. 4236–4257.
  * [47] H. Zhao, Q. Liu, G. Wang, Y. Ge, and E. Chen, Portfolio selections in p2p lending: A multi-objective perspective, in Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, 2016, pp. 2075–2084.