Near-Optimal Experimental Design for Networks: Independent Block Randomization
Dr. Chen Chen
Postdoctoral Researcher in Operations Management Area
Booth School of Business
University of Chicago
Motivated by the prevalence of experimentation in online platforms and social networks, we consider the problem of designing randomized experiments to assess the effectiveness of a new market intervention for a network of users. An experiment assigns each user to either the treatment or the control group. The outcome of each user depends on her assignment as well as the assignments of her neighbors. Given the experiment, the unbiased HorvitzThompson estimator is used to estimate the total market effect of the treatment. The decision maker chooses randomized assignments of users to treatment and control, in order to minimize the worst-case variance of this estimator. We focus on networks that can be partitioned into communities, where the users in the same community are densely connected, and users from different communities are only loosely connected. In such settings, it is almost without loss to assign all users in the same community to the same variant (treatment or control). The problem of designing the optimal randomized assignments of communities can be formulated as a linear program with an exponential number of decision variables and constraints in the number of communities – and hence, is generally computationally intractable.
We develop a family of practical experiments that we refer to as independent block randomization (IBR) experiments. Such an experiment partitions communities into blocks so that each block contains communities of similar sizes. It then treats half of the communities in each block (chosen uniformly at random) and does so independently across blocks. The optimal community partition can be obtained in a tractable way using dynamic programming. We show that these policies are asymptotically optimal when the number of communities grows large and no community size dominates the rest. In the special case where community sizes take values in a finite set and the number of communities of each size is a fixed proportion of the total number of communities, the loss is only a constant that is independent of the number of communities. Beyond the asymptotic regime, we show that the IBR’ experiment is a i-approximation for any problem instance. We also examine the performance of the IBR experiments on data-driven numerical examples, including examples based on Facebook subnetworks.
