Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
125,158 characters · 23 sections · 22 citation commands
Reducing Marketplace Interference Bias Via Shadow Prices
Modern technology companies use experiments to make {\color{black}many product} decisions {\color{black}both} minor (tweaking parameters) {\color{black}and} major (shipping new features). {\color{black}A} fundamental challenge in {\color{black}platform} experimentation is marketplace interference. For instance, consider a ride-hailing platform experimenting with a demand-side price discount. The platform performs a randomized control trial (RCT), or A/B test, where some demand units are offered the {\color{black}discount} while others are {\color{black}not}. Because the treated units are more likely to book rides as a result of the discount, they reduce the total supply available to all demand-side units, including the control units. This interference between treatment and control units causes the Stable Unit Treatment Value Assumption (SUTVA) to fail, and induces bias in the standard estimator used to {\color{black}measure} the value generated by the treatment.
A standard answer to this problem is to replace the “user-split” design, where individual units are randomly assigned to treatment and control, with a “time-split” (or “switchback”) design, where the entire market switches repeatedly between treatment and control. However, this design is {\color{black}in many cases} infeasible. Consider, for example, a user interface change that a user finds jarring or confusing at first, but eventually prefers to the original design after repeated exposure. A user-split experiment could easily capture such an effect, and analysts could even discard data from users' adjustment period at the start of the experiment. Meanwhile, a time-split design would repeatedly alternate between user interfaces over the duration of the experiment, a clearly undesirable outcome.
Instead of modifying the experimental design, {\color{black}in this paper} we propose a method for directly removing most interference bias from user-split experiments. Most existing works assume that removing bias from a marketplace user-split experiment is a very difficult task. Often, these papers consider experiments in platforms like Airbnb or Amazon where interference is caused by customer choice, which is difficult to model correctly {\color{black}and tractably}. In contrast, we consider generalized matching marketplaces, where the platform assigns supply units to demand units via a matching or network flow algorithm. Examples of such settings include ride-hailing, delivery, and supply chains. We argue that because such generalized matching platforms control the flow of units through the system, they have a great deal of knowledge about the interference structure. They can leverage this {\color{black}information} to remove most of the marketplace interference bias from user-split experiments.
We consider a model with a finite number of supply and demand types. Each type has a given Poisson arrival rate under the control policy. {\color{black}We consider a demand-side treatment which affects these demand arrival rates.} We do not assume the platform knows any of these arrival rates. The platform has a matching value $v_{i,j}$ for assigning a demand unit of type $i$ to a supply unit of type $j$. After collecting demand and supply requests for a certain amount of time, the platform runs a {\color{black}matching} cycle where it assigns supply units to demand units via a network flow linear program (LP). The platform's goal is to quantify the global treatment effect, i.e., the difference in value between the setting where all units are treated and the setting where no units are treated. Because these settings are not simultaneously observable, the platform {\color{black}must use} data from an experiment in which a fraction of users (treatment group) are exposed to treatment, while the remaining users (control group) are not.
The standard approach to this estimation problem is what we call the RCT estimator, which estimates the global treatment effect by comparing the total value obtained by treatment units with the total value obtained by control units. Our first main result is that, under a fairly broad condition, the RCT estimator systematically overestimates the global treatment effect. We show this result by taking the system to its fluid limit and showing, first, that the RCT estimator corresponds to a linear approximation of the value function, and second, that this linear approximation is of poor quality in the presence of interference. The condition is that the treatment effect is sign-consistent across types, which means that if the effect is positive for one type, then it is positive for all types. This condition is used to rule out examples where the RCT estimator overestimates the amplitude of both a positive treatment effect on one type and a negative effect on a different type in such a way that the total bias is zero. This would be an example of the standard estimator performing well due to luck rather than good design.
The fluid limit of the value function suggests a new potential approach to the problem: estimate the system arrival rate under both global treatment and global control, solve {\color{black}two} LPs to compute the value function under both global treatment and global control, and estimate the global treatment effect {\color{black}as} the difference between the value of these two LPs. We call this {\color{black}second} approach the Two-LP estimator. Our second main result is to prove that this estimator is unbiased in the fluid limit. However, this solution is not perfect: the estimate can be biased in a finite-sized system.
This motivates a third estimator, which we call the shadow price (SP) estimator. The SP estimator uses the shadow prices of the matching LP's constraints to calculate the value of the treatment. Intuitively, the shadow price of a demand constraint measures the incremental value of an additional unit of demand, and therefore captures the true value of increasing (or reducing) demand. Our next main result is that the SP estimator is less biased than the RCT estimator under a couple of conditions. The first condition is sign-consistency of the treatment effect. The second condition is that the experiment is symmetric: the control and treatment groups each represent 50% of the total population. We can {\color{black}either} relax this symmetry assumption with a modified estimator {\color{black}based on a} convex combination of the SP and RCT estimators, {\color{black}or replace it with the practically reasonable assumption that the treatment is not disruptive enough to meaningfully alter the interference pattern in the marketplace.}
Like the RCT estimator, the SP estimator is based on a linear approximation of the matching value function, and therefore it {\color{black}can be} biased. However, unlike the RCT estimator, the SP estimator uses the “correct” linear approximation, in the sense that it is the first-order Taylor series approximation of the value function. Crucially, we prove that the SP estimator is the correct linear approximation even in a finite-sized system, not just in the fluid limit. Therefore, it is not difficult to construct finite-sized instances where the Two-LP estimator is a lot more biased than the SP estimator.
{\color{black}Though our technique is designed with the treatment effect on the platform's objective function in mind, {\color{black}we show} it can be extended to measure effects on secondary objectives. In practice, firms running experiments often}ten} track a number of metrics {\color{black}beyond overall value}. {\color{black}We can use LP complemtary slackness to extend our shadow price technique to these secondary metrics.}
We validate our proposed method via two simulations. For the first simulation, we use publicly available data about New York City's taxi and ride-hailing ride requests over a given month. We construct a matching value metric based on efficiency defined as ride distance minus pickup distance. We simulate ride requests over a day and construct a matching cycle, then consider an experiment that increases ride request rates. We show that our proposed estimator greatly outperforms the RCT estimator and nearly matches the true global treatment effect. The second simulation captures a supply chain fulfillment experiment. Like the first simulation, it also demonstrates that the SP estimator is a great tool for reducing marketplace interference bias in experiments.
Interference in experiments is by now a well-known problem and an area of particular focus for recent literature, with empirical studies by blake2014marketplace and fradkin2019simulation showing that interference effects are quite significant in real-world experiments respectively involving auctions and recommendation systems. The bulk of the literature on this topic focuses on modifying classical experimental designs to reduce interference. In contrast, our paper considers a standard RCT design and proposes a method to reduce bias without modifying the experiment design.
Early works on this topic focused on experiments over social networks rather than marketplaces. In social network settings, the key concern is that treating a user might affect their peers. The most common method to address this problem involves a bucketing design (also known as a subplot or subnetwork design), where nodes that form a closely-knit group in some network sense are given the same treatment assignment (see, for instance, ugander2013graph). More recently, similar methods have been applied to estimate and reduce bias in marketplace experiments holtz2020reducing. In the social network setting, chin2019regression uses natural fluctuations in the randomized treatment assignment and constructs estimators that differentiate between users that have more neighbors in the control group (and can serve as a proxy for global control) and users that have more neighbors in the treatment group (and can serve as a proxy for global treatment).
Beyond bucketing, another {\color{black}widely used technique} is the switchback design or time-split, where an entire market is switched back and forth between treatment and control over time. This technique dates back all the way to cochran1939long but it has recently gained significant traction. For instance, bojinov2022design studies how to optimally design a switchback experiment. chamandy2016experimentation and sneider2019experiment discuss the use of switchback experiments at Lyft and Doordash, respectively. chamandy2016experimentation, in particular, discusses the tradeoffs between a bucketing-type approach and a switchback design. As discussed in Section (ref), switchback designs are not feasible for experiments that involve significant changes in the user interface.
More recently, johari2022experimental and bajari2021multiple have proposed experiment designs where the random assignment to treatment and control is applied to both supply and demand units simultaneously. While {\color{black}our analysis shares similar aspects} (such as large-scale limits), neither framework applies easily to our problem of interest. Both johari2022experimental and bajari2021multiple implicitly or explicitly describe marketplaces where supply and demand units interact directly (rather than through a matching algorithm), so supply-side {\color{black}and} demand-side experiment{\color{black}s are interchangeable for most treatments}. bajari2021multiple impose a local interference assumption which does not hold in our setting, while johari2022experimental use a choice model to capture spillovers. Under a similar marketplace model, li2022interference analyze the effect of the treatment proportion of supply-side and demand-side experiments on estimator variance and interference bias.
Another recent stream of work focuses on experiment designs that seek to measure the marginal effect of a treatment. wager2021experimenting consider experiments in which users are exposed to price shocks large enough to measure an effect, but small enough to preserve marketplace equilibrium. The paper then proposes an SGD-like method to construct a sequence of experiments that converge to the correct estimates despite the presence of interference. In contrast, our paper proposes a method to linearly approximate the interference structure of a single experiment. Our linear approximation is constructed using gradients in a matching marketplace; in the different context of a price-based multi-commodity market, munro2021treatment find that indirect treatment effects due to interference are related to direct treatment effects via utility gradients.
We consider a two-sided matching platform that collects supply and demand requests over time. We assume the platform collects requests over a period of time that we call a matching cycle and then matches them at the end of the cycle with the goal of maximizing some reward function.
\paragraph{Supply and demand types.} Each unit of supply or demand belongs to one of a finite number of types. We index demand types by $i=1,\ldots,n_d$ and supply types by $j=1,\ldots,n_s$. Supply units of type $j$ arrive according to a Poisson process with parameter $\pi_j$, and we denote the vector of supply arrival rates by $\bm{\pi}=\left(\pi_1, \ldots, \pi_{n_s}\right)$. Demand intent units of type $i$ arrive according to a Poisson process with parameter $\tilde{\lambda}_i$. Upon arrival, a demand intent unit observes some information about the state of the marketplace (such as a price or expected pick-up time), and chooses to make a request with probability $p_i$, which might depend on the marketplace state. Request realizations are assumed to be independent of each other and of the Poisson arrival processes. If a demand intent unit does not make a request, it leaves the marketplace forever. We will use the term demand units to refer to units that have submitted requests, as opposed to demand intent units, which might or might not have submitted requests. The arrival process of demand units is therefore a thinning of the demand intent arrival process and is a Poisson process itself with arrival rate $\lambda_i=\tilde{\lambda}_ip_i$ for demand units of type $i$. The demand arrival rates are denoted by $\bm{\lambda}=\left(\lambda_1, \ldots, \lambda_{n_d}\right)$.
We will use $\tau$ to denote a scaling parameter and use the vectors $\mathbf{D}^{\tau} = (D_1^\tau,...,D_{n_d}^\tau)$ and $\bm{S}^{\tau}=(S_1^\tau,...,S_{n_s}^\tau)$ to represent respectively the total number of demand and supply units of each type during a matching cycle. The scaling parameter allows us to consider different regimes where supply and demand arrivals are rare (low $\tau$) or frequent (high $\tau$) and can be thought of as the marketplace density. For each $i$ and $j$, $D_i^\tau$ and $S_j^\tau$ are Poisson-distributed random variables with respective means $\lambda_i \tau$ and $\pi_j \tau$.
\paragraph{{\color{black}Special case: bipartite matching.}} Given a set of supply and demand units, the platform's goal is to assign each demand unit to a supply unit. {\color{black}In order to build intuition, we first present the special case where the platform simply needs to solve a bipartite matching (or transportation) problem. In this case, the platform's optimization problem given demand $\mathbf{D}^{\tau}=\bm{d}$ and supply $\bm{S}^{\tau}=\bm{s}$ can be written as:}
The decision variables $x_{i,j}$ indicate the number of demand units of type $i$ {matched with} supply units of type $j$. Constraints (ref) and (ref) ensure that the matching is feasible from both the demand and supply sides. {\color{black}Because} the constraint matrix is totally unimodular, we can ignore integrality constraints on the decision variables.
\paragraph{General {\color{black}case:} matching via network flows.} {\color{black}Though the bipartite matching case is more intuitive, the results in this paper apply in a more general setting, where the platform's optimization problem is any minimum-cost network flow problem. The goal of the platform is still to connect demand units and supply units; however, it must now do so by pushing units of flow through an arbitrary capacitated network. More precisely, we are now given} a directed graph $\mathcal{G}=(\mathcal{U}, \mathcal{A})$. {\color{black}The node set $\mathcal{U}=\mathcal{U}_d\cup\mathcal{U}_s\cup\mathcal{U}_*$ contains three types of nodes: demand, supply, and intermediate.} The set $\mathcal{U}_d$ has one node for each demand type ($|\mathcal{U}_d|=n_d$), and the node $u^d_i$ corresponding to the $i$-th demand type is a sink with demand $D_i^\tau$; similarly, the set $\mathcal{U}_s$ has one node for each supply type ($|\mathcal{U}_s|=n_s$), and the node $u^s_j$ corresponding to the $j$-th supply type is a source with supply $S_j^\tau$. Intermediate nodes are neither sources nor sinks, and their set $\mathcal{U}_*$ can be arbitrarily large. To simplify notation and without loss of generality, we assume demand nodes (sinks) only have incoming edges and supply nodes (sources) only have outgoing edges, while intermediate nodes can have both incoming and outgoing edges. Given a demand vector $\mathbf{D}^{\tau}=\bm{d}$ and a supply vector $\bm{S}^{\tau}=\bm{s}$, we can write the platform's optimization problem as {\color{black}the} linear program:
The decision variable $x_{u,w}$ indicates the flow along arc $(u,w)$ in the graph. Constraints (ref) and (ref) ensure that we do not exceed demand and supply capacity; constraint (ref) ensures flow balance at each intermediate node. Finally, constraint (ref) imposes a capacity on each edge – note that this capacity also scales with $\tau$. Each unit of flow along arc $(u,w)$ generates a value $v_{u,w}$ to the platform. The problem is formulated as a value-maximization rather than a cost-minimization problem, but the two are mathematically equivalent. {\color{black}When the set of intermediate nodes $\mathcal{U}_*$ is empty, we recover the special case of bipartite matching. A diagram of our matching settings is shown in Figure (ref).}
{\color{black}As before}, since the constraint matrix of this problem is totally unimodular, we can relax the integer constraints {\color{black}and retain an integral} optimal solution. To avoid introducing more notation, we will use $\Phi_\tau(\cdot,\cdot)$ to represent both the LP itself and its optimal solution value, depending on the context. For $\tau=1$ we will drop the subscript altogether and refer to $\Phi(\cdot,\cdot)$.
We consider a treatment that affects the demand arrival rate to the platform. This treatment could involve a change in the user experience (e.g., a smartphone notification to increase engagement) or a financial incentive (e.g., a coupon). A key requirement is that the treatment should not affect the matching function, i.e., the matching algorithm should not distinguish between treated and untreated units. For clarity of exposition, we assume that the treatment does not affect the supply arrival rate. However, due to the symmetry of constraints (ref) and (ref), the framework extends to a treatment that only affects the supply arrival rate, or that jointly affects both the demand and supply arrival rates.
We assume that, if the change were to be rolled out to all demand intent units, the effect of the change would be to modify the request probability of a demand unit of type $i$ from $p_i$ to $p_i+q_i$, with $q_i\in[-p_i,1-p_i]$. From the perspective of the platform, this modification in request probability is equivalent to a change in demand arrival rates for the treatment group. We denote this change in arrival rate as $\bm{\beta}$, such that $\beta_i=\tilde{\lambda}_iq_i$. Evaluating the impact of our intervention means estimating the difference in value between the global treatment state, in which demand units arrive at rate $\bm{\lambda}+\bm{\beta}$, and the global control state, in which demand units arrive at rate $\bm{\lambda}$. For a particular scaling factor $\tau$, let $\bm{D}^{\tau, \bm{\lambda}}$ denote the realized demand vector with demand arrival rate $\bm{\lambda}$ (for simplicity, we maintain the notation of $\bm{S}^\tau$ instead of $\bm{S}^{\tau,\bm\pi}$ since our demand-side treatment does not affect supply). Our objective is to estimate the global treatment effect $\Delta^{\tau}$, which is defined as follows.
We include a $1/\tau$ term in front of the expectation in Definition (ref) because we are interested in a “scale-free” treatment effect, rather than the treatment effect for a system of a particular scale.
Unfortunately, we cannot directly observe the global treatment effect since we cannot simultaneously observe the marketplace under both global treatment and global control. Instead, we use a demand-split experiment design: we assign each demand unit upon arrival to the treatment group, with probability $\rho$, or the control group with probability $1-\rho$. Therefore, the arrival rate of treated demand units will be $\bm{\lambda}^{\text{treatment}} = \rho(\boldsymbol{\lambda}+\boldsymbol{\beta})$ and the arrival rate of control demand units will be $\bm{\lambda}^{\text{control}} = \left(1-\rho\right)\boldsymbol{\lambda}$, for an experiment demand arrival rate of:
Given a scaling factor $\tau$, we observe demand $\bm{D}^{\tau,\text{experiment}}=\bm{D}^{\tau,\text{control}} + \bm{D}^{\tau,\text{treatment}}$ in the experiment, where $D_i^{\tau,\text{control}}\sim \text{Poisson}(\lambda^{\text{control}}_i\tau)$ and $D_i^{\tau,\text{treatment}}\sim \text{Poisson}(\lambda^{\text{treatment}}_i\tau)$, implying that $D^{\tau,\text{experiment}}_i\sim \text{Poisson}(\lambda_i\tau + \rho\beta_i\tau)$. During the experiment, we obtain data by solving
In the following section we describe this experimental data in more detail.
When the platform solves the matching problem $\Phi(\bm{D}^{\tau,\text{experiment}},\bm{S}^\tau)$ during an experiment, it obtains data specifying the optimal match. {\color{black}We first describe this data in the special case of bipartite matching, then consider the general network flow case.}
\paragraph{{\color{black}Bipartite matching.}} {\color{black}By solving the matching linear program in the experiment state, the platform obtains two types of data. Primal data describes the optimal matching explicitly, and includes the number of control (respectively, treatment) demand units of type $i$ matched with supply units of type $j$, denoted by $X^{\tau,\text{control}}_{i,j}$ (respectively, $X_{i,j}^{\tau,\text{treatment}}$). Because the matching problem is a linear program, the platform also obtains dual data, in the form of an optimal solution to the dual of the LP in Eq. (ref). Given realized demand $\bm{d}$ and supply $\bm{s}$, the dual is another linear program, which can be written as:}
where $a_i$ corresponds to the shadow price of an additional unit of demand of type $i$, $b_j$ corresponds to the shadow price of an additional unit of supply of type $j$. Most linear programming algorithms provide an optimal dual solution “for free” along with the optimal primal solution (the optimal dual solution certifies the optimality of the primal solution). For an experiment with demand $\bm{D}^{\tau,\text{experiment}}=\bm{D}^{\tau,\text{control}}+\bm{D}^{\tau,\text{treatment}}$ and supply $\bm{S}^{\tau}$, we denote this dual data by $(\bm{A}^{\tau,\text{experiment}}, \bm{B}^{\tau,\text{experiment}})$.
\paragraph{{\color{black}General matching.}} {\color{black}In the general case, we similarly obtain primal and dual data. This time, the primal data must describe the number of demand units from the control group (respectively, treatment group) using each edge $(u,w)$ in the flow network, denoted by $X_{u,w}^{\tau,\text{control}}$ (respectively, $X_{u,w}^{\tau,\text{treatment}}$). We denote the total flow along edge $(u,w)$ by $X_{u,w}^{\tau,\text{experiment}}=X_{u,w}^{\tau,\text{control}}+X_{u,w}^{\tau,\text{treatment}}$.}
In addition to the flow along each edge, another, more interpretable primal quantity {\color{black}in the general case} is the number of demand units of type $i$ matched to supply units of type $j$, and more precisely the number matched via a particular path in the graph, since different paths may yield different values. We denote by $n_{i,j}$ the number of paths from the supply node $u_j^s$ to the demand node $u_i^s$. For the $p$-th such path, we denote by $Y_{i,j,p}^{\tau,\text{control}}$ (respectively $Y_{i,j,p}^{\tau,\text{treatment}}$) the number of demand units from the control group (respectively treatment group) matched to a supply unit of type $j$ via path $p$. The total number of demand units of type $i$ matched to a supply unit of type $j$ along path $p$ is written as $Y_{i,j,p}^{\tau,\text{experiment}}=Y_{i,j,p}^{\tau,\text{control}}+Y_{i,j,p}^{\tau,\text{treatment}}$. Each demand unit of type $i$ matched to a supply unit of type $j$ creates value $\nu_{i,j,p}=\sum_{(u,w)\in\mathcal{A}_{i,j,p}}v_{u,w}$, where $\mathcal{A}_{i,j,p}\subseteq \mathcal{A}$ designates the edges in path $p$ connecting supply node $u_j^s$ to demand node $u_i^d$.
{\color{black}We also obtain dual data in the general case.} Because demand nodes have no outgoing edges and supply nodes have no incoming edges, we can partition the edge set $\mathcal{A}$ into four types of edges: $\mathcal{A}_{s\to d}$ denotes the set of edges linking supply nodes to demand nodes, $\mathcal{A}_{s\to *}$ edges from supply nodes to intermediate nodes, $\mathcal{A}_{*}$ edges from intermediate nodes to other intermediate nodes, and $\mathcal{A}_{*\to d}$ edges from intermediate nodes to demand nodes. The dual of the general matching problem can then be formulated as follows:
{\color{black}As before}, $a_i$ corresponds to the shadow price of an additional unit of demand of type $i$, $b_j$ corresponds to the shadow price of an additional unit of supply of type $j$. {\color{black}The additional variable $\xi_{u,w}$} corresponds to the shadow price of increasing the capacity of edge $(u,w)$, {\color{black}while the} dual variable $m_u$ for each intermediate node $u\in\mathcal{U}_*$ can be thought of as defining a potential function which relates the demand and supply shadow prices via the paths that connect their respective nodes in the graph. {\color{black}These additional variables ensure correctness of the dual, but are not useful in our methodology. Only the shadow prices of demand and supply matter, which is why the bipartite matching example can be easier to reason about.} For an experiment with demand $\bm{D}^{\tau,\text{experiment}}=\bm{D}^{\tau,\text{control}}+\bm{D}^{\tau,\text{treatment}}$ and supply $\bm{S}^{\tau}$, we denote {\color{black}the} dual data by $(\bm{A}^{\tau,\text{experiment}}, \bm{B}^{\tau,\text{experiment}}, \bm{M}^{\tau,\text{experiment}}, \bm{\Xi}^{\tau,\text{experiment}})$.
\paragraph{{\color{black}Interchangeability of demand and control units.}} A key assumption of our framework is that treatment affects the arrival rate of demand units, but not the value they bring to the platform. In other words, the platform treats demand units in the treatment and control groups {\color{black}the same way}. As a result, there may be multiple optimal solutions, since a control and treatment unit of the same type can always be exchanged without affecting the objective value. We assume the platform selects between these optimal solutions at random, respecting the following assumption.
{\color{black}Assumption (ref) is motivated by practice; we would like the experiment to inform us about the state of the system under global control (where no units are treated) and under global treatment (where all units are treated). In both of these states, all units of the same type are interchangeable.}
In this section, we consider the most commonly used estimator for the treatment effect, and identify the source of its bias under marketplace interference.
Because randomized control trial designs are the workhorse of experimentation studies, there exists a standard estimator for the global treatment effect. We refer to it as the randomized control trial (RCT) estimator, often called Horvitz-Thompson estimator in the statistics literature.
In the equation above, the first term inside the parenthesis estimates the value of global treatment by re-scaling the value obtained from the treatment group by the treatment fraction $\rho$. Similarly, the second term estimates the value of global control by re-scaling the control group value by the control fraction $1-\rho$. Equivalently, the RCT estimator can be written as:
where the total value in each group is aggregated by summing over paths rather than edges.
In the special case of bipartite matching, the RCT estimator is given by
where $X_{i,j}^{\tau,\text{control}}$ (respectively $X_{i,j}^{\tau,\text{treatment}}$) marks the number of demand units of type $i$ from the control group (respectively treatment group) matched with a supply unit of type $j$. The edge-based and path-based definitions coincide {\color{black}because} there is a single edge between each supply and demand node. Comparing the {total value} obtained from the treatment group and the {total value obtained from the} control group is the standard estimation technique in randomized control trials.
Exact analysis of our discrete model can be challenging due to the stochasticity of the Poisson processes generating supply and demand. The challenge is particularly acute when the market is “thin” --- i.e., when the low density of supply and demand confers disproportionate influence to small variations in Poisson arrivals. Because these effects vanish when density increases, we {\color{black}study} a high-density limit of the system, where $\tau$ {\color{black}grows} arbitrarily large. For simplicity, we only consider integer densities $\tau$. {\color{black}A} key quantity of interest {\color{black}is} the fluid limit value for a given demand rate:
When density tends to infinity, we can ignore the stochastic fluctuations of the Poisson process and focus only on the expected number of demand and supply arrivals, given by the rates $\bm{\lambda}$ and $\bm{\pi}$. We now prove that the fluid limit value is given by the LP from Eq. (ref) where the inputs are the rates $\bm \lambda$ and $\bm \pi$ rather than realizations of demand and supply.
Theorem (ref) allows us to simplify our analysis {\color{black}by studying the deterministic linear program $\Phi(\bm \lambda, \bm \pi)$ in lieu of a complex stochastic system. The simplified system retains the key property under study, namely} the effect of marketplace contention for scarce supply. The first implication of Theorem (ref) is that it simplifies the expression for the global treatment effect from Definition (ref).
In the fluid limit, the global treatment effect is simply the difference between the optimal values of two linear programs. In contrast, running a demand-split experiment {\color{black}means considering} the “intermediate” linear program $\Phi(\bm \lambda^{\text{experiment}}, \bm \pi)=\Phi(\bm\lambda + \rho\bm\beta, \bm\pi)$. In effect, the experiment state interpolates between the global control and global treatment states. We formalize this notion of interpolation by introducing a useful tool, which we call the partial-treatment value function.
Using the partial-treatment value function, we can equivalently write the global treatment effect as $\Delta=\Psi(1)-\Psi(0)$. Under our demand-split experiment with treatment fraction $\rho$, we observe the total value $\Psi(\rho)$. Using classical results from linear programming, we can establish that $\Psi(\cdot)$ has a particular functional form, which will be useful in our analysis.
To guarantee that all estimators are well-defined in the fluid limit, we will also make the following assumption throughout the paper.
By allowing us to restrict our analysis to a deterministic setting, the fluid limit allows us to gain insight into the performance of the {standard} RCT estimator.
Proposition (ref) provides a simple explanation of the RCT estimator's behavior in the fluid limit: it first uses the experiment data to compute the average value obtained by each demand type $i$, called $\bar v_i^*$. It then estimates the value of treatment on group $i$ by multiplying $\bar v_i^*$ with $\beta_i$, which is the demand effect of the treatment on group $i$.
An easy way to understand what the RCT estimator does is to observe that it corresponds to building a specific linear approximation of the {matching} value function. In particular, it {notices that at the experiment point,} the value function verifies $\Phi(\bm {\lambda^{\text{experiment}}},\pi) = \bm{\bar v^*} \cdot \bm {\lambda^{\text{experiment}}}${, and assumes this linear relationship continues to apply when the demand is $\bm\lambda$ (global control) and $\bm\lambda + \bm\beta$ (global treatment). This approximation would be correct in the absence of marketplace interference.} In {its} presence{, however}, the value function is concave rather than linear (Proposition (ref)). {We can show that ignoring {\color{black}this concavity} introduces a systematic bias in the RCT estimator. Before we do so, we introduce our third and final assumption on the treatment effect.
}
Without this assumption, it is possible to construct an example with $\beta_1 > 0$ and $\beta_2 < 0$ where, due to interference, the RCT estimator simultaneously overestimates (in amplitude) the positive effect from the increased demand of type 1 and the negative effect from the decreased demand of type 2, in such a way that the respective biases (which have opposite signs) cancel. The resulting estimator can have zero bias, but this is due to a lucky coincidence rather than any inherent quality of the estimator. {All the results that follow rely on Assumptions (ref)-(ref) unless otherwise stated.}
We illustrate Theorem (ref) through a running example, visualized in Figure (ref). Consider a {bipartite matching} setting {\color{black}with} one demand type ($n_d=1$), with arrival rate $\lambda_1=1.5$ under control, and $\lambda_1+\beta=5.5$ under treatment. Additionally, we have six supply types ($n_s=6$), with $\pi_j=1$ and {\color{black}$v_{1,j}=2^{(2-j)}$} for each supply type $j$. Our example exhibits contention since the arrival rate of the highest-value supply $\pi_1=1$ is less than the arrival rate of demand $\lambda_1=1.5$ under control (and much less than under treatment). As a result, the function $\lambda \to \Phi(\lambda, \bm{\pi})$ is strictly concave. We plot this function in Figure (ref), noting that the true global treatment effect $\Delta$ {\color{black}equals} the difference in the function's value at $\lambda_1+\beta$ (global treatment) and its value at $\lambda_1$ (global control).
In an experimental setting, we cannot simultaneously evaluate the system value under both global control and global treatment; we {\color{black}can only} evaluate the value function at an intermediate state where $\lambda=\lambda_1+\rho\beta$ (in this case we assume $\rho=0.5$). Then, according to Proposition (ref), the RCT estimator constructs a linear approximation of the value function, defined using two points: the observed system value in the experiment state, and the known system value of 0 when demand is 0 (the origin). Figure (ref) shows this linear approximation, which corresponds to the RCT estimator, as a dashed line. {\color{black}Clearly,} the dashed line is not a particularly good approximation of the solid line{:} it simultaneously underestimates the system value under global control ($\bar{v}^*\lambda_1\le \Psi(0)$) while overestimating the system value under global treatment ($\bar{v}^*(\lambda_1+\beta)\ge \Psi(1)$). As a result, the RCT estimator is biased, and significantly so when the concavity of the value function is more pronounced. In the different context of choice-based marketplaces, li2022interference show an equivalent result to Theorem (ref) establishing the persistent overestimation behavior of standard estimators.
{We now propose a first alternative to the RCT estimator to reduce marketplace interference, which separately estimates the value function in the global control and global treatment states.}
Bias in the RCT estimator occurs because the estimator's implicit approximation of the value function does not take into account its concavity. We propose an alternative approach that does not require implicitly approximating the value function. {\color{black}Instead}, we use experiment data to estimate the demand arrival rates $\bm{\lambda}$ under global control and $\bm{\lambda}+\bm{\beta}$ under global treatment, as well as the supply arrival rates $\bm{\pi}$. We then use these estimated arrival rates to directly {\color{black}estimate} $\Phi(\bm{\lambda}+\bm{\beta}, \bm{\pi})$ and $\Phi(\bm{\lambda}, \bm{\pi})$. Intuitively, we construct {\color{black}estimated} counterfactual settings for global treatment and global control, then compute the optimal matching in both cases. Because this estimator involves setting up and solving two more linear programs, we refer to it as the Two-LP estimator.
The Two-LP estimator results from a two-step approach. First, the experimental data are used to estimate the Poisson arrival rates for demand under global control and under global treatment, as well as the supply arrival rates. The estimated rates, denoted by $\hat{\bm{\lambda}}(\cdot)$, $\hat{\bm{\beta}}(\cdot)$ and $\hat{\bm{\pi}}(\cdot)$ are then used to compute the counterfactual value under global control and under global treatment.
We can simplify {\color{black}the} Two-LP estimator using the standard {\color{black}Poisson} maximum-likelihood estimator. Given that the number of {\color{black}control} demand units of type $i$ is sampled from a Poisson process with parameter $(1-\rho)\lambda_i$, the maximum-likelihood estimators for $\lambda_i${\color{black}, $\beta_i$, and $\pi_j$ are} given by \[ \hat{\lambda}_i=\frac{D_i^{\tau,\text{control}}}{(1-\rho)\tau},~ \hat{\beta}_i=\frac{D_i^{\tau,\text{treatment}}}{\rho\tau}-\frac{D_i^{\tau,\text{control}}}{(1-\rho)\tau} \text{, and } \hat{\pi}_j=\frac{S_j^{\tau,\pi_j}}{\tau}, \] {\color{black}yielding} the following equivalent formulation for the Two-LP estimator.
Proposition (ref) provides a simple nonparametric intuition for the Two-LP estimator. Assume the experiment is symmetric ($\rho=0.5$). Then we estimate the total demand in the global control state by doubling the control demand in the experiment state. Similarly, we estimate the total demand in the global treatment state by doubling the treatment demand in the experiment state.
The Two-LP estimator seems like an ideal approach for the fluid limit problem, where we have a sufficient number of demand and supply units to estimate the Poisson arrival rates for both demand and supply exactly. Indeed, we can show this estimator is unbiased in the fluid limit.
\paragraph{Theoretical limitations.} We have established that the Two-LP estimator is asymptotically unbiased in the fluid limit. However, the fluid limit is an idealized setting {\color{black}where $\tau$ is large}; it turns out that in a finite-sample setting, the Two-LP estimator does not necessarily remain unbiased. Recall that the global treatment effect we seek to estimate is given by: \[ \Delta^\tau=\frac{1}{\tau}\mathbb{E}\left[\Phi\left(\bm{D}^{\tau,\bm{\lambda}+\bm{\beta}}, \bm{S}^{\tau,\bm{\pi}}\right)-\Phi\left(\bm{D}^{\tau,\bm{\lambda}},\bm{S}^{\tau,\bm{\pi}}\right)\right]. \]
In contrast, the expected value of the Two-LP estimator can be written as: \[ \mathbb{E}[\hat{\Delta}^\tau_{\text{2LP}}]=\frac{1}{\tau}\mathbb{E}\left[\Phi\left(\frac{1}{\rho}\bm{D}^{\tau,\rho(\bm{\lambda+\beta})}, \bm{S}^{\tau,\bm{\pi}}\right)-\Phi\left(\frac{1}{1-\rho}\bm{D}^{\tau,(1-\rho)\bm{\lambda}},\bm{S}^{\tau,\bm{\pi}}\right)\right]. \]
The main difference between these two expectations is that the former relies on the Poisson-distributed vector $\bm{D}^{\tau,\bm{\lambda}+\bm{\beta}}$ (respectively $\bm{D}^{\tau,\bm{\lambda}}$) while the latter uses the rescaled ---and therefore not Poisson-distributed--- vector $\frac{1}{\rho}\bm{D}^{\tau,\rho(\bm{\lambda+\beta})}$ (respectively $\frac{1}{1-\rho}\bm{D}^{\tau,(1-\rho)\bm{\lambda}}$). {\color{black}The rescaled demand vector has higher variance due to the $1/\rho$ factor; since the value function $\Phi(\cdot)$ is also nonlinear, the two expectations do not equal each other for finite $\tau$. We next show that for small $\tau$, there exist settings} where the Two-LP estimator exhibits considerable bias.
{\color{black}We can construct such a problem instance by considering} a bipartite matching instance with an equal number of demand and supply types. Each demand unit of type $i$ generates a value of 1 when matched with a supply unit of type $j=i$, and 0 otherwise; the capacity of the edge from the demand node for type $i$ to the supply node for type $j=i$ is also 1. We set low arrival rates such that the Poisson arrival processes in both global control and global treatment are well approximated by Bernoulli processes, i.e., each demand type has either zero or one arrivals. With $\rho=0.5$, the Two-LP estimator estimates the value of global treatment by doubling the number of treated units, and estimates the value of global control by doubling the number of control units. However, doubling the number of units will yield no additional value due to the capacity constraint on each type, whereas doubling the arrival rates (as we would under global control and global treatment) does increase total value to the platform. {\color{black}Similar flaws arise when $\rho\to 0$ or $\rho\to 1$; we note that the bias is positive in one case and negative in the other, which means the two-LP estimator can get not only the magnitude but also the sign of the intervention wrong.} The capacity constraint is not essential to our construction{\color{black}; supply could play the constraining role instead, but using capacity simplifies the analysis.} We {\color{black}illustrate} our construction in Figure (ref).
{\color{black}Proposition (ref) establishes that increased variance due to rescaling Poisson processes together with nonlinearity of the value function can lead to bias in the finite-sample setting. This bias disappears in the large-$\tau$ limit as variance goes to zero. It also increases as the experiment becomes more asymmetric and $1/\rho$ or $1/(1-\rho)$ grow large. We verify this behavior numerically in Section (ref).}
\paragraph{Computational limitations.} In addition to this theoretical limitation in the finite-sample setting, the Two-LP estimator also suffers from practical limitations. First, because it requires solving two additional linear programs, it is more computationally intensive than the standard RCT estimator, which simply adds quantities obtained from the experiment matching linear program. This additional overhead can become cumbersome if we consider multiple matching cycles, or if we wish to perform additional analyses such as permutation tests, which require recomputing test statistics many times. Second, the Two-LP estimator requires access to the matching value function to simulate the counterfactual outcomes under global treatment and global control. Maintaining a simulation environment to perform this analysis might be a significant engineering task, for example {\color{black}if the} matching {\color{black}environment relies on} real-time signals that are difficult to replicate offline.
We now propose another estimator to reduce interference bias. In a way, this estimator interpolates between the RCT and Two-LP estimators. Like the former, it can be computed directly from experimental data, without solving additional optimization problems. Like the latter, it reduces interference bias as compared to the standard estimator.
The RCT estimator can be biased in a marketplace setting because it does not account for the diminishing returns of additional demand units in a marketplace with constrained supply. This concept requires a notion of marginal value of demand, which we model via LP duality. Recall that in our experiment, we obtain the dual data $(\bm{A}^{\tau,\text{experiment}}, \bm{B}^{\tau,\text{experiment}}, \bm{M}^{\tau,\text{experiment}}, \bm{\Xi}^{\tau,\text{experiment}})$.
In particular, ${A}_i^{\tau,\text{experiment}}$ {\color{black}is} the marginal value (or shadow price) of a demand unit of type $i$. We can define an analog to the RCT estimator, where instead of summing the total value obtained by the treatment and control groups, we sum the total marginal value obtained by each group.
Like the RCT estimator, the SP estimator consists of two terms: the first estimates the value of global treatment, while the second estimates the value of global control. However, rather than simply scaling the values of the control and treatment groups in the experiment, {\color{black}we} rely on linear programming sensitivity analysis to extrapolate the values of global treatment and global control.
In {Section (ref)}, we showed that the RCT estimator {implicitly} uses a linear approximation of the value function to estimate the global treatment effect. Using a linear approximation of the value function to estimate the global treatment effect is not a bad idea. The problem with the RCT estimator is that it uses the wrong linear approximation. {\color{black}We now} argue that the SP estimator uses the correct linear approximation of the partial-treatment value function at the experiment state.
Let $\bm{a}^{\eta}$ denote the optimal {demand} dual variables associated with the partial-treatment matching problem {in the fluid limit} $\Phi(\bm{\lambda}+\eta\bm{\beta}, \bm{\pi})$. We {\color{black}first} derive {\color{black}the} fluid limit of the SP estimator.
Proposition (ref) establishes that the SP estimator is also based on a linear approximation of the value function. However, this approximation is constructed using first-order information obtained from the shadow prices of the matching problem. The dual variables $\bm a^\rho$ correspond to the marginal values {\color{black}of additional} demand units {\color{black}of each type}. {\color{black}The} inner product with $\bm \beta$ {\color{black}is} the gain in the objective value predicted by the constraint shadow prices (locally optimal in a Taylor series sense).
We provide evidence of this result in Figure (ref). In the same example {from Section (ref) (recall Figure (ref) for setup details),} we draw the shadow price-based linear approximation (dashdotted line) and the resulting SP estimator. Like the RCT estimator, the SP estimator tends to overestimate the value of global treatment. However, due to the concavity of the value function, it also overestimates the value of global control. Depending on the relative magnitude of these two biases, the SP estimator can over- or underestimate the treatment effect. {We next show how the SP estimator reduces bias (in absolute terms) as compared to the RCT estimator.}
\paragraph{Bias reduction.} Both the RCT and SP estimators rely on the implicit construction of a linear approximation of the partial-treatment value function $\Psi(\cdot)$. The main difference is that the RCT estimator determines the slope of its implicit approximation using the average value $\bar{v}^*_i$ obtained from each type $i$, whereas the SP estimator uses the marginal value obtained from type $i$, as captured by the shadow price $a^\rho_i$. It turns out there is a fundamental reason why $a^\rho_i$ is a useful quantity in estimating the global treatment effect $\Delta$. Recalling from Proposition (ref) that $\Psi(\cdot)$ is a piecewise linear function with finitely many pieces, which implies it is Riemann-integrable, we can {\color{black}rewrite the global treatment effect $\Delta$ using the fundamental theorem of calculus.}
Using this framework, we can directly compare the bias of the RCT and SP estimators, by comparing the true partial-treatment value function $\Psi(\cdot)$ and the respective linear approximations $\hat{\Psi}_{\text{RCT}}$ and $\hat{\Psi}_{\text{SP}}$ implicitly constructed by the RCT and SP estimators. In particular, we can now prove {a core} result of this paper: {\color{black}under our assumptions,} it is always possible to design an experiment such that the SP estimator is less biased than the RCT estimator.
The proof of Theorem (ref) separately considers the case of a consistently positive treatment effect ($\bm\beta\ge 0$) and a consistently negative treatment effect ($\bm\beta\le0$). We summarize the proof of the former case graphically in Figure (ref), noting that our reasoning is analogous in the latter case. The proof relies on exposing no more than half the population to treatment, i.e., $\rho\le0.5$. Conversely, when the treatment effect is consistently negative, we should expose no less than half the population to treatment. Symmetric experiments ($\rho=0.5$) satisfy both constraints, which is useful since we typically do not know a priori whether the treatment effect is consistently positive or negative. {Symmetric experiments are often used in practice because they tend to minimize variance; however, in some situations, rolling a treatment out to half of the marketplace may be too costly. We discuss this issue further in Section (ref) and propose {\color{black}two} simple methods to address it.}
\paragraph{Variance reduction.} The SP estimator also improves upon the RCT estimator in terms of variance. The following result compares the asymptotic variances of the two estimators.
The variance of the SP estimator is tricky to analyze {because the breakpoints in the piecewise linear matching function can make it difficult to estimate the second derivative of the partial-treatment value function.} However, in the fluid limit, the probability that the system operates at a breakpoint in the partial-treatment value function goes to 0. In this setting, the RCT {(respectively SP) estimator is the product of the average (respectively marginal) value of a type with the increase in demand for that type. Because the average value is always greater than or equal to the marginal value, the RCT estimator is more sensitive to variance in demand.}
{\color{black}U}nlike our characterization of bias, Theorem (ref) does not require sign-consistency of the treatment effect on demand $\bm\beta$. When analyzing bias, sign-consistency {\color{black}precludes} the case where the RCT estimator overestimates both the positive effect from increased demand of one type and the negative effect from decreased demand of another type, in such a way that the biases cancel. When it comes to variance, however, overestimating the magnitude of either a positive or negative effect will result in the same contribution to overall variance. Theorem (ref) suggests that the bias correction obtained via the shadow price estimator does not come at the expense of low variance.
{ {\color{black}The} SP estimator reduces bias as compared to the standard RCT estimator in the fluid limit. However, unlike the Two-LP estimator, it {\color{black}may} not eliminate interference bias altogether in this setting. We now explore why the SP estimator may {\color{black}still} be preferable to the Two-LP estimator.
In particular, performance in the fluid limit does not tell the whole story. Indeed, Proposition (ref) shows that the Two-LP estimator can be strongly biased in the finite-sample regime. It is therefore of interest to study the behavior of the SP estimator in the finite-sample case. We first define the generalization of the partial-treatment function to the finite-sample setting:
By construction, the scaled finite-sample partial-treatment value function $\Psi_{\tau}(\eta)$ tends to the partial-treatment value function $\Psi(\eta)$, i.e. $\Psi(\eta)=\lim_{\tau\to\infty}\Psi_\tau(\eta)$. Like $\Psi(\cdot)$, $\Psi_\tau(\cdot)$ is concave and continuous. However, while $\Psi(\cdot)$ is piecewise linear, $\Psi_\tau(\cdot)$ is smooth -- its derivative is uniquely defined everywhere. In the finite-sample setting, the {\color{black}random} arrivals on the supply and demand side effectively “smooth out” the breakpoints in the underlying value function. Once again, the global treatment effect verifies $\Delta^\tau=\Psi_{\tau}(1)-\Psi_{\tau}(0)$. {\color{black}We now establish} that, as in the fluid limit, the SP estimator results from a first-order approximation of the partial-treatment value function.
}
{ Theorem (ref) states that the shadow price estimator correctly estimates the derivative of the partial-treatment value function at the experiment state ($\eta=\rho$). This principled behavior immediately allows us to bound the expected bias of the shadow price estimator as follows.
Superficially, Theorem (ref) seems like an intuitive result: taking the difference in total marginal value between the treatment and control group yields the “correct” derivative of the partial-treatment value function. However, the proof is nontrivial, and relies on the particular form of the Poisson probability mass function, as well as the dual structure of the generalized matching problem. The proof also relies on the following result, which might be of independent interest.}
{ Proposition (ref) (LP sensitivity analysis) tells us that the function $\Phi_\tau(\cdot,\cdot)$ is concave and piecewise linear. Theorem (ref) further tells us that for any particular supply/demand configuration, the matching value function is linear in any sufficiently small perturbation in demand. The result allows us to define subgradients of the value function $\bm{a}^+$ and $\bm{a}^-$, such that:
These two subgradients are identical {\color{black}when} the matching value function is locally linear, and the optimal shadow prices are unique ($\bm{a}^+=\bm{a}^-=\bm{a}$). {\color{black}This corresponds to Assumption (ref), which is reasonable in the fluid limit} since the rates $\bm{\lambda}$, $\bm{\beta}$ and $\bm{\pi}$ are real numbers. However, in the finite-sample setting, the optimal solution may be degenerate, i.e, the optimal dual solution may not be unique. In this case, we can choose any optimal dual solution. Two choices are $a_i^+$ and $a_i^-$: the marginal value of adding a unit of demand of type $i$, and the marginal value of removing a unit of demand of type $i$. {\color{black}Intuitively, we} are more interested in the latter, therefore, when the optimal shadow prices are not unique, we select $a_i=a_i^-$. {\color{black}This also turns out to be the right choice to ensure Theorem (ref) holds.} We discuss how to compute $\bm{a}^+$ and $\bm{a}^-$ in Section (ref). }
{So far, we have established that the SP estimator reduces bias from the RCT estimator in the fluid limit, and remains well-behaved in the finite-sample regime. However, {\color{black}bias reduction} depends on a symmetric experimental design, i.e., where $\rho=0.5$. This assumption is limiting: in practice, platforms may want to roll out a potentially expensive or risky treatment to a much smaller fraction of the market. We now explore ways to {\color{black}relax} this assumption. We begin with a counter-example that shows what happens in the fluid limit when the symmetric design is violated.}
We can prove Proposition (ref) by constructing such an example. We consider a single demand type ($n_d=1$) and supply type ($n_s=1$), verifying $\lambda_1=0$ (demand in global control), $\beta_1=1$ (demand in global treatment), and $\pi_1=0.625$ (supply level). We obtain value $v_{1,1}=1$ from each supply-demand match. We {\color{black}let} $\rho=0.75$. The example is {\color{black}shown} in Figure (ref).
In this example the SP estimator is unbiased for global treatment but overestimates global control. Meanwhile the RCT estimator is unbiased for global control but overestimates global treatment. Due to the asymmetric design, overestimating global control turns out to be “worse” than overestimating global treatment. {\color{black}We note that this counter-example} {requires} a significant discontinuity in the partial-treatment value function.
For a fixed treatment fraction $\rho\neq0.5$, we can construct examples where the SP estimator performs poorly. {\color{black}An initial mechanism to guard against such realizations is to randomize $\rho$.}
Theorem (ref) relies on the simple observation that taking the expectation of the SP estimator in the fluid limit means integrating $\hat{\Delta}_{\text{RCT}}=\bm{a}^{\rho}\cdot\bm{\beta}$ over the interval $[0,1]$, which is precisely the definition of the true global treatment effect given by Proposition (ref). {The same result applies in the finite-sample case using Theorem (ref).} {\color{black}U}nlike Theorem (ref), {\color{black}this result} does not rely on sign-consistency of the treatment effect $\bm\beta$. However, its {\color{black}usefulness} may be limited, since selecting the treatment fraction at random has other drawbacks, both theoretical ({increased} variance) and practical ({incompatible with a fixed experiment budget}).
{In practice, experimenters may wish to expose only a very small fraction $\rho \ll 0.5$ of the marketplace to the treatment, particularly if the treatment is expensive or the experiment has a finite budget. Fortunately, if the treatment effect on demand is positive, i.e., $\bm{\beta}\ge \bm{0}$, the result from Theorem (ref) extends to any $\rho \le 0.5$. However, if $\bm{\beta}\le\bm{0}$, and we correspondingly observe a negative value of $\hat{\Delta}_{\text{SP}}$, there is a possibility (outlined in Proposition (ref)) that the shadow price estimator is more biased than the standard estimator.}
{One way to achieve our bias reduction objective is to construct a new estimator which is a convex combination of the shadow price and standard estimators. By combining the two estimators, we can ensure that we always reduce bias as compared to the standard estimator.}
{
}
{ By inspecting the definition, we see that the SP+ estimator behaves more like the SP estimator when the treatment fraction $\rho$ tends to 0.5, and more like the RCT estimator when the treatment fraction $\rho$ tends to zero. This behavior allows the SP+ estimator to leverage the shadow price estimator's bias reduction without succumbing to pathological cases like the one described in Proposition (ref). We formalize this intuition in Theorem (ref).
Theorem (ref) establishes that the SP+ estimator always guarantees a reduction in bias. When we observe a negative treatment effect with $\rho<0.5$, we can therefore use the SP+ estimator instead of the SP estimator. If we observe a positive treatment effect, then we can stick with the SP estimator. We can also construct a symmetric version of the SP+ estimator which guarantees bias reduction when $\rho > 0.5$ and $\bm{\beta}\ge \bm{0}$, i.e., \[ \hat{\Delta}_{\text{\emph{SP+}}}=(2\rho-1)\,\hat{\Delta}_{\text{\emph{RCT}}}+2(1-\rho)\,\hat{\Delta}_{\text{\emph{SP}}}. \] We omit the analogous statement of Theorem (ref) (which trivially holds by symmetry) to this case, for brevity and because exposing more than half of customers to treatment is practically unrealistic. }
{\color{black}Theorems (ref) and (ref) provide provable ways to reduce bias for asymmetric experiments. However, we will see numerically that the bias of the shadow price estimator is usually much lower than the bias of the RCT estimator, even in asymmetric experiments. Indeed, the counter-example presented in Proposition (ref) is pathological --- in global control, there is no interference to speak of, while in global treatment, there is so much interference that the partial-treatment value function in Figure (ref) is flat. In practice, the interventions that platforms experiment with are almost always marginal. It is therefore unlikely that the intervention itself is fundamentally altering the structure of interference in the marketplace. We can therefore introduce the following result guaranteeing bias reduction for any treatment fraction.
The first part of Theorem (ref) guarantees that the shadow price estimator reduces bias as long as the left-hand side of (ref) is larger than the right-hand side. The left-hand side is large if there is significant interference in the marketplace in global control, namely, average values are larger than marginal values. The right-hand side is small if the structure of interference is similar in global control and global treatment. These conditions are often satisfied in practice: indeed, if it is the case that interference is very weak in global control and very strong in global treatment, a single experiment is unlikely to be the right tool to assess the impact of the proposed intervention. The second part of Theorem (ref) also guarantees that the shadow price estimator is unbiased as long as the interference pattern is exactly the same in global control and global treatment.
Unlike Theorems (ref) and (ref), the conditions described in Theorem (ref) are not verifiable from the experiment state, as they require knowledge of the shadow prices under global treatment and global control. However, as we see in Section (ref), they often hold in practice.
}
{We now validate our theoretical results on estimator performance using real and simulated data. We show that we can improve performance as compared to the standard estimator, even when we depart from some of our theoretical assumptions.}
{We first consider a ride-hailing setting simulated using data from the NYCdata, which catalogs roughly 10 million origin-destination pairs from June 2023 taxi rides in New York City. From this large dataset, we can construct simulated problem instances as follows: we independently sample $n_d$ origins, representing ride requests and $n_s$ destinations, representing drivers (assuming drivers remain in the area where they dropped off their last passenger). Ride requests and drivers are randomly assigned a time within 24 hours. Drivers can be matched to a request if it appears within 15 minutes of the driver appearing on the platform. Riders must be matched to drivers already on the platform. The value of matching request $i$ to driver $j$ is given by a notion of efficiency: $v_{i,j}=d^{\text{ride}}_i - d^{\text{pickup}}_{i,j}$, where $d_i^\text{ride}$ is the length of ride $i$ in miles (from the data) and $d^\text{pickup}_{i,j}$ is the (Haversine) pickup distance from driver $j$ to request $i$. We assume that the platform does not need to fulfill rides with negative efficiency. For tractability, we simplify the graph to only allow matches between a request and its 40 closest drivers.}
{This first simulation environment is designed to stretch the limits of our discrete-type assumption. Because we consider each ride request and driver to be its own distinct type (due to its unique location in space and time), there is always exactly one unit of each type. While this simulation allows us to test our method on a real dataset, one downside of this explosion of types is that it leads to primal degeneracy:} since the optimal primal solution is binary, every variable $x_{i,j}^*=1$ simultaneously satisfies both a demand and a supply capacity constraint to equality. {We discussed how to handle multiple duals in Section (ref), by choosing the “lower sugradient” $a_i^-$. Thanks to Theorem (ref), {\color{black}all these lower subgradients} can be computed efficiently by reducing the value of the right-hand side of each demand constraint by $0<\varepsilon<1/n_d$.}
{We consider twelve experimental settings, with four levels of contention for supply {\color{black}(2000, 4000, 8000, and 16000 requests, against 16000 drivers)} and three magnitudes of the treatment effect on the arrival rate of demand (3%, 5%, 10%). For each of these twelve settings, we sample the appropriate number of requests and drivers 80 times. For each sample, we randomly assign rides in equal proportions to treatment and control, then we capture the treatment effect by randomly removing an appropriate fraction of requests from the control group. We repeat this treatment-control assignment and down-sampling 20 times for each sampled supply-demand graph, and we report the average of the true global treatment effect, as well as the average values of the RCT, SP, and Two-LP estimators. We then plot the median of our 80 replications in Figure (ref). }
Our results show marketplace interference {arising} from the contention between {requests} when supply levels are low {relative to demand}. When contention is high we see that the {increase in total efficiency due to} new {requests} is smaller than the {increase in demand}, by up to 20%. Due to interference, this effect is not captured in the standard RCT estimator which produces a biased estimate that remains stubbornly proportional to $e$; in contrast, the SP estimator {and Two-LP estimator} manage to eliminate nearly all the bias induced by network effects, {for all effect magnitudes}.
In {Figure (ref)} we show the median standard deviation of the actual treatment effect and {all estimators across all replications of a single configuration}. {As the number of drivers increases, estimator variance decreases. Furthermore, the RCT estimator typically has the most variance, and the gap with the other two estimators increases as the number of requests increases.}
We next consider a simple supply chain network from ahuja1988network, displayed in Figure (ref). The network has two plant nodes and two retail nodes, connected via two layers of warehouses consisting of 5 nodes each. We augment the network with capacities and costs, which are fixed for all simulations. Each edge has a maximum capacity $k_{u,w}$ sampled from a Poisson distribution with parameter 80, and a cost $c_{u,w}$ sampled uniformly from $[0,5]$. The fixed cost of production per unit is $\kappa_1=37$ in plant 1 and $\kappa_2=20$ in plant 2. The price per unit is $p_1=50$ at retailer 1 and $p_2=60$ at retailer 2. The value $v_{u,w}$ of an edge is given by $-c_{u,w}$ for all intermediate edges, $-c_{u,i}+p_{i}$ for all edges $(u,i)$ going into retailer node $i$, and $-c_{j,w}-\kappa_j$ for all edges $(j,w)$ coming out of plant node $j$.
W{e assume} the plants $p_1$ and $p_2$ have production capacities $S_1\sim\text{Poisson}(\pi_1=130)$ and $S_2\sim\text{Poisson}(\pi_2=190)$. The demand $D_1$ at retailer $r_1$ and $D_2$ at retailer $r_2$ are also Poisson random variables with parameters $\lambda_1$ and $\lambda_2$ which we will vary as part of the simulation. The treatment introduces a demand change $\beta_1$ at retailer $r_1$ and $\beta_2$ at retailer $r_2$. {In particular, we} consider two scenarios for the demand arrival rates $\bm{\lambda}$: an undersupply scenario where $\bm\lambda=(130,120)$, and an oversupply scenario where $\bm\lambda=(60,60)$. We {study five} possible treatment effects of varying magnitude and sign: $\boldsymbol{\beta}\in\{ {\footnotesize\left(10,10\right),\left(20,20\right),\left(-10,-10\right)}$, $\footnotesize{\left(-20,20\right),\left(20,-20\right)}\}.$ Readers will notice that the effects are not always sign-consistent.
{\color{black}W}e first compute the true global treatment effect by separately simulating the control and treatment settings with respective demand arrival rates $\bm\lambda$ and $\bm\lambda+\bm\beta$. Then we simulate an experiment with treatment fraction $\rho=0.5$ and compute the RCT{, SP, and Two-LP} estimators. {Results are shown} in Figure (ref), where each vertical bar represents the average over 1000 simulations, and each group of vertical bars corresponds to a particular treatment effect on demand $\bm\beta$.
In Figure (ref), we observe the result in the oversupplied regime. As predicted by the theory, the RCT estimator always overestimates the magnitude of the global treatment effect, while the SP estimator {and the Two-LP estimator} sometimes overestimate and sometimes underestimate the effect. Nevertheless, the differences between {all} the estimators are small since there is minimal contention for supply. {In contrast}, the results in Figure (ref) {reveal a} pronounced {difference between the estimators, with the RCT estimator systematically overestimating the magnitude of the treatment effect by more than a factor of two. The SP estimator consistently reduces bias, even when the treatment is not sign-consistent.}
{Finally, we study the performance of our estimators in asymmetric experiments, i.e., experiments where the fraction of units assigned to the treatment group is (much) smaller than 50%. We consider the same undersupply setting presented in Figure (ref) ($\bm\lambda=(130,120)$), and repeat the same analysis, but this time with $\rho=0.1$ and $\rho=0.01$. Results are shown in Figure (ref).
First, we verify that the SP+ estimator, which we introduced to achieve provable bias reduction over the RCT estimator for any $\rho$, does accomplish this task. However, it remains significantly outperformed by the simpler SP estimator, indicating that the guarantee of bias reduction afforded by the SP+ estimator comes at a steep cost. Most strikingly, the performance of the Two-LP estimator deteriorates sharply as the treatment fraction shrinks. It appears that when the treatment group is small, we observe a similar small-sample issue as the one we analyzed in Proposition (ref). Figure (ref) displays a setting where the shadow price estimator performs far better in practice than the theory can guarantee.
}
Most of the literature on interference in marketplaces is built on the implicit assumption the standard mechanism to match supply and demand is consumer choice. Under this assumption, our ability to directly model the interference structure between users is limited by the fundamental challenge of accurately modeling choice dynamics. Not all marketplaces are choice-based, however; matching-based platforms that assign supply units to demand units via algorithmic matching are also common. In such marketplaces, the structure of interference is actually mostly accessible to the platform: the shadow prices associated with the supply and demand constraints of the matching LP directly measure the incremental value of additional demand and supply units. {\color{black}We use this idea} with the specific aim of correcting interference bias in marketplace experiments. The matching LP shadow prices can likely prove to be a broadly applicable metric for matching-based platforms in any use case where the signal of interest is the marginal value of a unit of supply or demand.
\singlespacing \onehalfspacing