Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective

References

• Abadie A , Imbens GW (2006) Large sample properties of matching estimators for average treatment effects. Econometrica 74(1):235–267.Crossref, Google Scholar
• Abadie A , Imbens GW (2012) A martingale representation for matching estimators. J. Amer. Statist. Assoc. 107(498):833–843.Crossref, Google Scholar
• Ahuja RK , Magnanti TL , Orlin JB (1988) Network flows. Working paper, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Alaei S , Hajiaghayi M , Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. 13th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 18–35.Google Scholar
• Alweiss R , Liu YP , Sawhney M (2021) Discrepancy minimization via a self-balancing walk. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 14–20.Google Scholar
• Arlotto A , Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Ashlagi I , Roth AE (2012) New challenges in multihospital kidney exchange. Amer. Econom. Rev. 102(3):354–359.Crossref, Google Scholar
• Ashlagi I , Burq M , Dutta C , Jaillet P , Saberi A , Sholley C (2019) Edge weighted online windowed matching. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 729–742.Google Scholar
• Athey S , Imbens GW (2017) The econometrics of randomized experiments. Handbook of Economic Field Experiments , vol. 1 (Elsevier, Amsterdam), 73–140.Crossref, Google Scholar
• Atkinson AC (1982) Optimum biased coin designs for sequential clinical trials with prognostic factors. Biometrika 69(1):61–67.Crossref, Google Scholar
• Atkinson AC (1999) Optimum biased-coin designs for sequential treatment allocation with covariate information. Statist. Medicine 18(14):1741–1752.Crossref, Google Scholar
• Bai Y (2022) Optimality of matched-pair designs in randomized controlled trials. Amer. Econom. Rev. 112(12):3911–3940.Crossref, Google Scholar
• Bai Y , Romano JP , Shaikh AM (2022) Inference in experiments with matched pairs. J. Amer. Statist. Assoc. 117(540):1726–1737.Crossref, Google Scholar
• Bakshy E , Eckles D , Bernstein MS (2014) Designing and deploying online field experiments. Proc. 23rd Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 283–292.Google Scholar
• Bansal N , Jiang H , Singla S , Sinha M (2020) Online vector balancing and geometric discrepancy. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1139–1152.Google Scholar
• Bansal N , Jiang H , Meka R , Singla S , Sinha M (2021) Online discrepancy minimization for stochastic arrivals. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2842–2861.Google Scholar
• Basse G , Ding Y , Toulis P (2019) Minimax crossover designs. Preprint, submitted August 9, https://arxiv.org/abs/1908.03531.Google Scholar
• Bertsimas D , Tsitsiklis JN (1997) Introduction to Linear Optimization , vol. 6 (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D , Johnson M , Kallus N (2015) The power of optimization over randomization in designing experiments involving small samples. Oper. Res. 63(4):868–876.Link, Google Scholar
• Bhat N , Farias VF , Moallemi CC , Sinha D (2020) Near-optimal A-B testing. Management Sci. 66(10):4477–4495.Link, Google Scholar
• Bojinov I , Simchi-Levi D , Zhao J (2020) Design and analysis of switchback experiments. Preprint, submitted September 15, http://dx.doi.org/10.2139/ssrn.3684168.Google Scholar
• Buchbinder N , Naor J (2009) The Design of Competitive Online Algorithms via a Primal-Dual Approach (Now Publishers Inc., Boston).Crossref, Google Scholar
• Bumpensanti P , Wang H (2018) A re-solving heuristic with uniformly bounded loss for network revenue management. Preprint, submitted February 17, https://arxiv.org/abs/1802.06192.Google Scholar
• Candogan O , Chen C , Niazadeh R (2021) Near-optimal experimental design for networks: Independent block randomization. Preprint, submitted June 1, http://dx.doi.org/10.2139/ssrn.3852100.Google Scholar
• Chase G (1968) On the efficiency of matched pairs in Bernoulli trials. Biometrika 55(2):365–369.Crossref, Google Scholar
• Chen Q , Jasin S , Duenyas I (2016) Real-time dynamic pricing with minimal and flexible price adjustment. Management Sci. 62(8):2437–2455.Link, Google Scholar
• Chen Q , Lei Y , Jasin S (2023a) Real-time spatial–intertemporal pricing and relocation in a ride-hailing network: Near-optimal policies and the value of dynamic pricing. Oper. Res. , ePub ahead of print April 3, https://doi.org/10.1287/opre.2022.2425.Google Scholar
• Chen Y , Kanoria Y , Kumar A , Zhang W (2023b) Feature based dynamic matching. Preprint, submitted June 1, http://dx.doi.org/10.2139/ssrn.4451799.Google Scholar
• Cochran WG , Cox GM (1957) Experimental Designs (John Willey & Sons, New York), 546–568.Google Scholar
• Cox DR (1958) Planning of Experiments (Wiley, Hoboken, NJ).Google Scholar
• Cytrynbaum M (2021) Designing representative and balanced experiments by local randomization. Preprint, submitted November 16, https://arxiv.org/abs/2111.08157.Google Scholar
• Dehejia RH , Wahba S (2002) Propensity score-matching methods for nonexperimental causal studies. Rev. Econom. Statist. 84(1):151–161.Crossref, Google Scholar
• Derigs U (1988) Solving non-bipartite matching problems via shortest path techniques. Ann. Oper. Res. 13(1):225–261.Crossref, Google Scholar
• Devanur NR , Jain K , Kleinberg RD (2013) Randomized primal-dual analysis of ranking for online bipartite matching. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 101–107.Google Scholar
• Diamond A , Sekhon JS (2013) Genetic matching for estimating causal effects: A general multivariate matching method for achieving balance in observational studies. Rev. Econom. Statist. 95(3):932–945.Crossref, Google Scholar
• Efron B (1971) Forcing a sequential experiment to be balanced. Biometrika 58(3):403–417.Crossref, Google Scholar
• Feldman J , Mehta A , Mirrokni V , Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. 2009 Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 117–126.Google Scholar
• Fisher RA (1936) Design of experiments. BMJ 1(3923):554.Crossref, Google Scholar
• Fournier N , Guillin A (2015) On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Related Fields 162(3–4):707–738.Crossref, Google Scholar
• Gan Y (2023) Essays on dynamic optimization for markets and networks. Unpublished PhD thesis, Columbia University, New York.Google Scholar
• Goel G , Mehta A (2008) Online budgeted matching in random input models with applications to Adwords. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 982–991.Google Scholar
• Greevy R , Lu B , Silber JH , Rosenbaum P (2004) Optimal multivariate matching before randomization. Biostatistics 5(2):263–275.Crossref, Google Scholar
• Gupta S , Kohavi R , Tang D , Xu Y , Andersen R , Bakshy E , Cardin N , et al. (2019) Top challenges from the first practical online controlled experiments summit. SIGKDD Explorations Newsletter 21(1):20–35.Crossref, Google Scholar
• Harshaw C , Sävje F , Spielman D , Zhang P (2019) Balancing covariates in randomized experiments with the Gram–Schmidt Walk design. Preprint, submitted November 8, https://arxiv.org/abs/1911.03071.Google Scholar
• Higgins MJ , Sävje F , Sekhon JS (2016) Improving massive experiments with threshold blocking. Proc. Natl. Acad. Sci. USA 113(27):7369–7376.Crossref, Google Scholar
• Huang S , Wang C , Yuan Y , Zhao J , Zhang J (2023) Estimating effects of long-term treatments. Preprint, submitted February 13, http://dx.doi.org/10.2139/ssrn.4352459.Google Scholar
• Imai K , King G , Nall C (2009) The essential role of pair matching in cluster-randomized experiments, with application to the Mexican universal health insurance evaluation. Statist. Sci. 24(1):29–53.Crossref, Google Scholar
• Imbens GW (2011) Experimental design for unit and cluster randomid trials. Internat. Initiative Impact Evaluation (Harvard University, Cambridge, MA).Google Scholar
• Imbens GW , Rubin DB (2015) Causal Inference in Statistics, Social, and Biomedical Sciences (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Jaillet P , Lu X (2014) Online stochastic matching: New algorithms with better bounds. Math. Oper. Res. 39(3):624–646.Link, Google Scholar
• Jasin S (2014) Reoptimization and self-adjusting price control for network revenue management. Oper. Res. 62(5):1168–1178.Link, Google Scholar
• Jasin S , Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313–345.Link, Google Scholar
• Johari R , Koomen P , Pekelis L , Walsh D (2022a) Always valid inference: Continuous monitoring of A/B tests. Oper. Res. 70(3):1806–1821.Link, Google Scholar
• Johari R , Li H , Liskovich I , Weintraub GY (2022b) Experimental design in two-sided platforms: An analysis of bias. Management Sci. 68(10)7069–7089.Link, Google Scholar
• Kalyanasundaram B , Pruhs K (1993) Online weighted matching. J. Algorithms 14(3):478–488.Crossref, Google Scholar
• Kanoria Y (2021) Dynamic spatial matching. Preprint, submitted May 16, https://arxiv.org/abs/2105.07329.Google Scholar
• Kapelner A , Krieger A (2014) Matching on-the-fly: Sequential allocation with higher power and efficiency. Biometrics 70(2):378–388.Crossref, Google Scholar
• Karp RM , Vazirani UV , Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• Kernan WN , Viscoli CM , Makuch RW , Brass LM , Horwitz RI (1999) Stratified randomization for clinical trials. J. Clinical Epidemiology 52(1):19–26.Crossref, Google Scholar
• Kohavi R , Henne RM , Sommerfield D (2007) Practical guide to controlled experiments on the web: Listen to your customers not to the hippo. Proc. 13th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 959–967.Google Scholar
• Kohavi R , Tang D , Xu Y (2020) Trustworthy Online Controlled Experiments: A Practical Guide to A/B Testing (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Kohavi R , Crook T , Longbotham R , Frasca B , Henne R , Ferres JL , Melamed T (2009) Online experimentation at Microsoft. van der Putten PMelli G , Kitts B , eds. Data Mining Case Studies (Association for Computing Machinery, New York), 11–23.Google Scholar
• Koning R , Hasan S , Chatterji A (2019) Experimentation and startup performance: Evidence from a/b testing. NBER Working Paper No. 26278, National Bureau of Economic Research, Cambridge, MA.Google Scholar
• Lei Y , Jasin S (2020) Real-time dynamic pricing for revenue management with reusable resources, advance reservation, and deterministic service time requirements. Oper. Res. 68(3):676–685.Link, Google Scholar
• Lewis RA (2010) Where’s the “wear-out?”: Online display ads and the impact of frequency. Unpublished PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Lewis RA , Rao JM (2015) The unfavorable economics of measuring the returns to advertising. Quart. J. Econom. 130(4):1941–1973.Crossref, Google Scholar
• Li KC (1983) Minimaxity for randomized designs: Some general results. Ann. Statist. 11(1):225–239.Crossref, Google Scholar
• Li H , Zhao G , Johari R , Weintraub GY (2021) Interference, bias, and variance in two-sided marketplace experimentation: Guidance for platforms. Preprint, submitted April 25, https://arxiv.org/abs/2104.12222.Google Scholar
• Lu B , Greevy R , Xu X , Beck C (2011) Optimal nonbipartite matching and its statistical applications. Amer. Statist. 65(1):21–30.Crossref, Google Scholar
• Matts JP , Lachin JM (1988) Properties of permuted-block randomization in clinical trials. Controlled Clinical Trials 9(4):327–344.Crossref, Google Scholar
• Mehta A (2013) Online matching and ad allocation. Theoret. Comput. Sci. 8(4):265–368.Google Scholar
• Mehta A , Saberi A , Vazirani U , Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• Öncan T , Zhang R , Punnen AP (2013) The minimum cost perfect matching problem with conflict pair constraints. Comput. Oper. Res. 40(4):920–930.Crossref, Google Scholar
• Pocock SJ , Simon R (1975) Sequential treatment assignment with balancing for prognostic factors in the controlled clinical trial. Biometrics 31(1):103–115.Crossref, Google Scholar
• Rosenbaum PR (1989) Optimal matching for observational studies. J. Amer. Statist. Assoc. 84(408):1024–1032.Crossref, Google Scholar
• Rosenberger WF , Lachin JM (2015) Randomization in Clinical Trials: Theory and Practice (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Rosenberger WF , Sverdlov O (2008) Handling covariates in the design of clinical trials. Statist. Sci. 23(3):404–419.Crossref, Google Scholar
• Roth AE , Sönmez T , Ünver MU (2004) Kidney exchange. Quart. J. Econom. 119(2):457–488.Crossref, Google Scholar
• Rubin DB (2008) Comment: The design and analysis of gold standard randomized experiments. J. Amer. Statist. Assoc. 103(484):1350–1353.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency , vol. 24 (Springer, Berlin).Google Scholar
• Spencer J (1977) Balancing games. J. Combin. Theory Ser. B 23(1):68–74.Crossref, Google Scholar
• Vera A , Banerjee S (2019) The Bayesian prophet: A low-regret framework for online decision making. Abstracts 2019 SIGMETRICS/Performance Joint Internat. Conf. Measurement Model. Comput. Systems (Association for Computing Machinery, New York), 81–82.Google Scholar
• Wager S , Xu K (2021) Experimenting in equilibrium. Management Sci. 67(11):6694–6715.Link, Google Scholar
• Wu CF (1981) On the robustness and efficiency of some randomized designs. Ann. Statist. 9(6):1168–1177.Crossref, Google Scholar
• Xiong R , Athey S , Bayati M , Imbens GW (2019) Optimal experimental design for staggered rollouts. Preprint, submitted November 20, http://dx.doi.org/10.2139/ssrn.3483934.Google Scholar