Süleyman Kerimov
I am a final year Ph.D. student in Operations Research at Stanford University, I am interested in market design, matching and applied probability. I use tools from economics, mathematics and operations research to design and analyze policies for marketplaces to achieve efficient outcomes. My thesis focuses on frictions that arise due to stochasticity and liquidity in matching markets. Here is my CV. You can contact me at kerimov at stanford dot edu. |
We study centralized dynamic matching markets with finitely many agent types and heterogeneous match values.
A network topology
describes the pairs of agent types that can form a match and the value generated from each match. A matching policy is hindsight optimal
if the policy can (nearly)
maximize the total value simultaneously at all times. We find that suitably designed greedy policies are hindsight
optimal in two-way matching networks.
This implies that there is essentially no positive externality from having agents waiting to form
future matches. We first show that the greedy longest-queue policy with a minor variation is hindsight optimal.
Importantly, the policy is
greedy relative to a residual network, which includes only non-redundant matches with respect to the static optimal matching rates. Moreover,
when the residual network is acyclic
(e.g., as in two-sided networks), we prescribe a greedy static priority policy that is also hindsight optimal.
The priority order of this policy is robust to arrival rate perturbations that do not alter the residual network. Hindsight optimality is closely
related to the lengths of type-specific queues.
Queue-lengths cannot be smaller (in expectation) than \(O(1/\epsilon)\), where \(\epsilon\) is the general position gap
that quantifies the stability in the network. The greedy longest-queue policy achieves this lower bound.
We study how to optimally match agents in a dynamic market with heterogeneous match values. A network topology determines the feasible
matches in the market.
We consider networks that are two-sided when all matches include two agents, or acyclic otherwise. An inherent trade-off
arises between generating short- and long-term value.
We find that when the network satisfies a general position condition, this trade-off is limited,
and a simple periodic clearing policy (nearly) maximizes the total value simultaneously at all times. Central
to our results is the general position gap,
\(\epsilon\), which quantifies the stability or the imbalance in the network. No policy can achieve a regret that is lower than the order of
\(1/\epsilon\) at all times. This
lower bound is achieved by a policy, which periodically resolves a natural LP, provided that the delay between periods is of the order of \(1/\epsilon\).
Examples illustrate the necessity of some delay in periodic clearing policies.
In economies without monetary transfers, scrip systems serve
an alternative to sustain cooperation, improve efficiency and mitigate free
riding.
This paper considers a marketplace, in which at each time period,
one agent requests a service, one agent provides the service, and a unit
of artificial
currency is used to pay for service provision. We ask whether
agents can sustain cooperation when the market is thin, in the sense that
only few
agents are available to provide the requested service. To study
this problem, we analyze the stability of the scrip distribution assuming that among
the available agents, the one with the minimum amount
of scrips is selected to provide service. When exactly one random agent
is available to
provide service, the scrip distribution is unstable, since
the number of scrips each agent has behaves like a simple random walk
in one dimension.
However, already when just two random agents are
available to provide service, the scrip distribution is stable, in the sense
that agents do not deviate
much from their initial endowment, with high
probability. This suggests that even with minimal liquidity in the market, cooperation can be sustained by
balancing service provisions among
agents. We further explore cases, in which agents request and become
available to provide service at different rates,
and generalize our positive
results to the case, in which the request and availability rates of each
agent are equal. Our theory builds on the literature on
the power of two
choices paradigm and load balancing problems. Finally, our results suggest that scrip systems can lead to efficient outcomes in kidney
exchange
platforms by sustaining cooperation between hospitals.