Near-Optimal Experimental Design Under the Budget Constraint in Online Platforms
Authors: 
Yongkang Guo, Yuan Yuan, Jinshan Zhang, Yuqing Kong, Zhihua Zhu, Zheng CaiAuthors Info & Claims
Pages 3603 - 3613
Abstract
A/B testing, or controlled experiments, is the gold standard approach to causally compare the performance of algorithms on online platforms. However, conventional Bernoulli randomization in A/B testing faces many challenges such as spillover and carryover effects. Our study focuses on another challenge, especially for A/B testing on two-sided platforms – budget constraints. Buyers on two-sided platforms often have limited budgets, where the conventional A/B testing may be infeasible to be applied, partly because two variants of allocation algorithms may conflict and lead some buyers to exceed their budgets if they are implemented simultaneously. We develop a model to describe two-sided platforms where buyers have limited budgets. We then provide an optimal experimental design that guarantees small bias and minimum variance. Bias is lower when there is more budget and a higher supply-demand rate. We test our experimental design on both synthetic data and real-world data, which verifies the theoretical results and shows our advantage compared to Bernoulli randomization.
References
[1]
Shipra Agrawal and Nikhil R Devanur. 2014. Fast algorithms for online stochastic convex programming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 1405–1424.
[2]
Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. 2014. A dynamic near-optimal algorithm for online linear programming. Operations Research 62, 4 (2014), 876–890.
[3]
Nick Arnosti, Marissa Beck, and Paul Milgrom. 2016. Adverse selection and auction design for internet display advertising. American Economic Review 106, 10 (2016), 2852–66.
[4]
Peter M Aronow and Cyrus Samii. 2013. Estimating average causal effects under interference between units. arXiv preprint arXiv:1305.6156 3, 4 (2013), 16.
[5]
Peter M Aronow and Cyrus Samii. 2017. Estimating average causal effects under general interference, with application to a social network experiment. The Annals of Applied Statistics 11, 4 (2017), 1912–1947.
[6]
Santiago R Balseiro, Omar Besbes, and Gabriel Y Weintraub. 2015. Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science 61, 4 (2015), 864–884.
[7]
Guillaume W Basse, Hossein Azari Soufiani, and Diane Lambert. 2016. Randomization and the pernicious effects of limited budgets on auction experiments. In Artificial Intelligence and Statistics. PMLR, 1412–1420.
[8]
Rahul Bhagat, Srevatsan Muralidharan, Alex Lobzhanidze, and Shankar Vishwanath. 2018. Buy it again: Modeling repeat purchase recommendations. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 62–70.
[9]
Thomas Blake and Dominic Coey. 2014. Why marketplace experimentation is harder than it seems: The role of test-control interference. In Proceedings of the fifteenth ACM conference on Economics and computation. 567–582.
[10]
Iavor Bojinov, David Simchi-Levi, and Jinglong Zhao. 2020. Design and analysis of switchback experiments. Available at SSRN 3684168 (2020).
[11]
Xiao Alison Chen and Zizhuo Wang. 2015. A dynamic learning algorithm for online matching problems with concave returns. European Journal of Operational Research 247, 2 (2015), 379–388.
[12]
Yan Chen and Joseph Konstan. 2015. Online field experiments: a selective survey of methods. Journal of the Economic Science Association 1, 1 (2015), 29–42.
[13]
Nikhil R Devanur and Thomas P Hayes. 2009. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce. 71–78.
[14]
Nikhil R Devanur and Kamal Jain. 2012. Online matching with concave returns. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing. 137–144.
[15]
Steven Diamond and Stephen Boyd. 2016. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research 17, 83 (2016), 1–5.
[16]
Pavel Dmitriev, Brian Frasca, Somit Gupta, Ron Kohavi, and Garnet Vaz. 2016. Pitfalls of long-term online controlled experiments. In 2016 IEEE international conference on big data (big data). IEEE, 1367–1376.
[17]
Dean Eckles, Brian Karrer, and Johan Ugander. 2017. Design and analysis of experiments in networks: Reducing bias from interference. Journal of Causal Inference 5, 1 (2017).
[18]
Lorenzo Fattorini. 2006. Applying the Horvitz-Thompson criterion in complex designs: a computer-intensive perspective for estimating inclusion probabilities. Biometrika 93, 2 (2006), 269–278.
[19]
Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S Mirrokni, and Cliff Stein. 2010. Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms. Springer, 182–194.
[20]
Anupam Gupta and Marco Molinaro. 2016. How the experts algorithm can help solve lps online. Mathematics of Operations Research 41, 4 (2016), 1404–1431.
[21]
Viet Ha-Thuc, Avishek Dutta, Ren Mao, Matthew Wood, and Yunli Liu. 2020. A counterfactual framework for seller-side a/b testing on marketplaces. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. 2288–2296.
[22]
David Holtz, Ruben Lobel, Inessa Liskovich, and Sinan Aral. 2020. Reducing interference bias in online marketplace pricing experiments. arXiv preprint arXiv:2004.12489 (2020).
[23]
Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. 2020. Adwords in a panorama. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 1416–1426.
[24]
[24] Jianwei Yin Jinshan Zhang, Xiaotie Deng. 2022. Private Communication.
[25]
Ramesh Johari, Hannah Li, Inessa Liskovich, and Gabriel Y Weintraub. 2022. Experimental design in two-sided platforms: An analysis of bias. Management Science (2022).
[26]
Thomas Kesselheim, Klaus Radke, Andreas Tonnis, and Berthold Vocking. 2018. Primal beats dual on online packing LPs in the random-order model. SIAM J. Comput. 47, 5 (2018), 1939–1964.
[27]
Samir Khan and Johan Ugander. 2021. Adaptive normalization for IPW estimation. arXiv preprint arXiv:2106.07695 (2021).
[28]
Ron Kohavi, Alex Deng, Roger Longbotham, and Ya Xu. 2014. Seven rules of thumb for web site experimenters. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 1857–1866.
[29]
Ron Kohavi and Roger Longbotham. 2011. Unexpected results in online controlled experiments. ACM SIGKDD Explorations Newsletter 12, 2 (2011), 31–35.
[30]
Ron Kohavi, Roger Longbotham, Dan Sommerfield, and Randal M Henne. 2009. Controlled experiments on the web: survey and practical guide. Data mining and knowledge discovery 18, 1 (2009), 140–181.
[31]
Young Kwark, Gene Moo Lee, Paul A Pavlou, and Liangfei Qiu. 2021. On the spillover effects of online product reviews on purchases: Evidence from clickstream data. Information Systems Research 32, 3 (2021), 895–913.
[32]
Min Liu, Jialiang Mao, and Kang Kang. 2021. Trustworthy and Powerful Online Marketplace Experimentation with Budget-split Design. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 3319–3329.
[33]
Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In Proceedings of the forty-third annual ACM symposium on Theory of computing. 597–606.
[34]
Marco Molinaro and Ramamoorthi Ravi. 2014. The geometry of online packing linear programs. Mathematics of Operations Research 39, 1 (2014), 46–59.
[35]
Lev Muchnik, Sinan Aral, and Sean J Taylor. 2013. Social influence bias: A randomized experiment. Science 341, 6146 (2013), 647–651.
[36]
Renato Paes Leme, Martin Pal, and Sergei Vassilvitskii. 2016. A field guide to personalized reserve prices. In Proceedings of the 25th international conference on world wide web. 1093–1102.
[37]
Jean Pouget-Abadie, Guillaume Saint-Jacques, Martin Saveski, Weitao Duan, S Ghosh, Y Xu, and Edoardo M Airoldi. 2019. Testing for arbitrary interference on experimentation platforms. Biometrika 106, 4 (2019), 929–940.
[38]
David Puelz, Guillaume Basse, Avi Feller, and Panos Toulis. 2019. A graph-theoretic approach to randomization tests of causal effects under general interference. arXiv preprint arXiv:1910.10862 (2019).
[39]
Donald B Rubin. 2005. Causal inference using potential outcomes: Design, modeling, decisions. J. Amer. Statist. Assoc. 100, 469 (2005), 322–331.
[40]
Johan Ugander, Brian Karrer, Lars Backstrom, and Jon Kleinberg. 2013. Graph cluster randomization: Network exposure to multiple universes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 329–337.
[41]
Yuan Yuan, Kristen Altenburger, and Farshad Kooti. 2021. Causal Network Motifs: Identifying Heterogeneous Spillover Effects in A/B Tests. In Proceedings of the Web Conference 2021. 3359–3370.
[42]
Yuan Yuan and Kristen M Altenburger. 2022. A Two-Part Machine Learning Approach to Characterizing Network Interference in A/B Testing. SSRN (2022).
Index Terms
- Near-Optimal Experimental Design Under the Budget Constraint in Online Platforms
Recommendations
Advertising versus brokerage model for online trading platforms
The two leading online consumer-to-consumer platforms use very different revenue models: eBay.com in the United States uses a brokerage model in which sellers pay eBay on a transaction basis, whereas Taobao.com in China uses an advertising model in ...
Platform Equilibrium: Analyzing Social Welfare in Online Market Places
EC '24: Proceedings of the 25th ACM Conference on Economics and ComputationWe introduce the theoretical study of a Platform Equilibrium in a market with unit-demand buyers and unit-supply sellers. Each seller can join a platform and transact with any buyer or remain off-platform and transact with a subset of buyers whom she ...
Near-optimal online auctions
SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithmsWe consider the online auction problem proposed by Bar-Yossef, Hildrum, and Wu [4] in which an auctioneer is selling identical items to bidders arriving one at a time. We give an auction that achieves a constant factor of the optimal profit less an O(h) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2023
4293 pages
ISBN:9781450394161
DOI:10.1145/3543507
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 April 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Tencent Marketing Solution
Conference
WWW '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 126Total Downloads
- Downloads (Last 12 months)30
- Downloads (Last 6 weeks)6
Reflects downloads up to 22 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format