Near-Optimal Experimental Design for Networks: Independent Block Randomization

A Google TechTalk, presented by Rad Niazadeh, 2021/09/30 ABSTRACT: 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 Horvitz-Thompson 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 exponential number of decision variables and constraints in the number of communities -- and hence is in general 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 7/3-approximation for any problem instance. We also examine the performance of the IBR experiments on data-driven numerical examples, including an example based on a Facebook subnetwork. Based on a joint work with Ozan Candogan and Chen Chen https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3852100 Bio: Rad Niazadeh is an Assistant Professor at the University of Chicago Booth School of Business in the operations management area. Prior to joining Booth, he was a postdoc researcher in the market algorithms group at Google Research NYC and a Motwani postdoctoral fellow at Stanford University, Department of Computer Science. He received his PhD in Computer Science (minored in Applied Mathematics) from Cornell University. Rad studies the interplay between algorithms, incentives, and learning, with the goal of advancing the theoretical methodologies and foundations of market design and operations in dynamic and complex environments. He has received the INFORMS Revenue Management and Pricing Dissertation Award (honorable mention) in 2018, the Google PhD Fellowship in Market Algorithms in 2016, the Stanford Motwani fellowship in 2017, and the Cornell Jacobs fellowship in 2012 for his research.