IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2011.02330.html
   My bibliography  Save this paper

Adaptive Combinatorial Allocation

Author

Listed:
  • Maximilian Kasy
  • Alexander Teytelboym

Abstract

We consider settings where an allocation has to be chosen repeatedly, returns are unknown but can be learned, and decisions are subject to constraints. Our model covers two-sided and one-sided matching, even with complex constraints. We propose an approach based on Thompson sampling. Our main result is a prior-independent finite-sample bound on the expected regret for this algorithm. Although the number of allocations grows exponentially in the number of participants, the bound does not depend on this number. We illustrate the performance of our algorithm using data on refugee resettlement in the United States.

Suggested Citation

  • Maximilian Kasy & Alexander Teytelboym, 2020. "Adaptive Combinatorial Allocation," Papers 2011.02330, arXiv.org.
    • Handle: RePEc:arx:papers:2011.02330
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2011.02330
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Carpenter, Bob & Gelman, Andrew & Hoffman, Matthew D. & Lee, Daniel & Goodrich, Ben & Betancourt, Michael & Brubaker, Marcus & Guo, Jiqiang & Li, Peter & Riddell, Allen, 2017. "Stan: A Probabilistic Programming Language," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 76(i01).
    2. Eric M. Schwartz & Eric T. Bradlow & Peter S. Fader, 2017. "Customer Acquisition via Display Advertising Using Multi-Armed Bandit Experiments," Marketing Science, INFORMS, vol. 36(4), pages 500-522, July.
    3. Maximilian Kasy & Anja Sautmann, 2021. "Adaptive Treatment Assignment in Experiments for Policy Choice," Econometrica, Econometric Society, vol. 89(1), pages 113-132, January.
    4. Narges Ahani & Tommy Andersson & Alessandro Martinello & Alexander Teytelboym & Andrew C. Trapp, 2021. "Placement Optimization in Refugee Resettlement," Operations Research, INFORMS, vol. 69(5), pages 1468-1486, September.
    5. Bryan S. Graham & Guido W. Imbens & Geert Ridder, 2010. "Measuring the Effects of Segregation in the Presence of Social Spillovers: A Nonparametric Approach," NBER Working Papers 16499, National Bureau of Economic Research, Inc.
    6. Jean-Yves Audibert & Sébastien Bubeck & Gábor Lugosi, 2014. "Regret in Online Combinatorial Optimization," Mathematics of Operations Research, INFORMS, vol. 39(1), pages 31-45, February.
    7. David Delacrétaz & Scott Duke Kominers & Alexander Teytelboym, 2023. "Matching Mechanisms for Refugee Resettlement," American Economic Review, American Economic Association, vol. 113(10), pages 2689-2717, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Maximilian Kasy & Alexander Teytelboym, 2020. "Adaptive targeted infectious disease testing," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 36(Supplemen), pages 77-93.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Maximilian Kasy & Alexander Teytelboym, 2023. "Matching with semi-bandits," The Econometrics Journal, Royal Economic Society, vol. 26(1), pages 45-66.
    2. Keisuke Hirano & Jack R. Porter, 2023. "Asymptotic Representations for Sequential Decisions, Adaptive Experiments, and Batched Bandits," Papers 2302.03117, arXiv.org.
    3. Davide Viviano & Jess Rudder, 2020. "Policy design in experiments with unknown interference," Papers 2011.08174, arXiv.org, revised Dec 2023.
    4. Magnus Lodefalk & Fredrik Sjöholm & Aili Tang, 2022. "International trade and labour market integration of immigrants," The World Economy, Wiley Blackwell, vol. 45(6), pages 1650-1689, June.
    5. Francis,David C. & Kubinec ,Robert, 2022. "Beyond Political Connections : A Measurement Model Approach to Estimating Firm-levelPolitical Influence in 41 Economies," Policy Research Working Paper Series 10119, The World Bank.
    6. Martinovici, A., 2019. "Revealing attention - how eye movements predict brand choice and moment of choice," Other publications TiSEM 7dca38a5-9f78-4aee-bd81-c, Tilburg University, School of Economics and Management.
    7. Yongping Bao & Ludwig Danwitz & Fabian Dvorak & Sebastian Fehrler & Lars Hornuf & Hsuan Yu Lin & Bettina von Helversen, 2022. "Similarity and Consistency in Algorithm-Guided Exploration," CESifo Working Paper Series 10188, CESifo.
    8. Yu Ding & Wayne S. DeSarbo & Dominique M. Hanssens & Kamel Jedidi & John G. Lynch & Donald R. Lehmann, 2020. "The past, present, and future of measurement and methods in marketing analysis," Marketing Letters, Springer, vol. 31(2), pages 175-186, September.
    9. Torsten Heinrich & Jangho Yang & Shuanping Dai, 2020. "Growth, development, and structural change at the firm-level: The example of the PR China," Papers 2012.14503, arXiv.org.
    10. van Kesteren Erik-Jan & Bergkamp Tom, 2023. "Bayesian analysis of Formula One race results: disentangling driver skill and constructor advantage," Journal of Quantitative Analysis in Sports, De Gruyter, vol. 19(4), pages 273-293, December.
    11. Preil, Deniz & Krapp, Michael, 2022. "Bandit-based inventory optimisation: Reinforcement learning in multi-echelon supply chains," International Journal of Production Economics, Elsevier, vol. 252(C).
    12. Xin Xu & Yang Lu & Yupeng Zhou & Zhiguo Fu & Yanjie Fu & Minghao Yin, 2021. "An Information-Explainable Random Walk Based Unsupervised Network Representation Learning Framework on Node Classification Tasks," Mathematics, MDPI, vol. 9(15), pages 1-14, July.
    13. Chao Qin & Daniel Russo, 2024. "Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification," Papers 2402.10592, arXiv.org.
    14. Xiaoyue Xi & Simon E. F. Spencer & Matthew Hall & M. Kate Grabowski & Joseph Kagaayi & Oliver Ratmann & Rakai Health Sciences Program and PANGEA‐HIV, 2022. "Inferring the sources of HIV infection in Africa from deep‐sequence data with semi‐parametric Bayesian Poisson flow models," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 71(3), pages 517-540, June.
    15. Masahiro Kato & Masaaki Imaizumi & Takuya Ishihara & Toru Kitagawa, 2023. "Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds," Papers 2302.02988, arXiv.org, revised Jul 2023.
    16. Kuschnig, Nikolas, 2021. "Bayesian Spatial Econometrics and the Need for Software," Department of Economics Working Paper Series 318, WU Vienna University of Economics and Business.
    17. Deniz Aksoy & David Carlson, 2022. "Electoral support and militants’ targeting strategies," Journal of Peace Research, Peace Research Institute Oslo, vol. 59(2), pages 229-241, March.
    18. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    19. Richard Hunt & Shelton Peiris & Neville Weber, 2022. "Estimation methods for stationary Gegenbauer processes," Statistical Papers, Springer, vol. 63(6), pages 1707-1741, December.
    20. D. Fouskakis & G. Petrakos & I. Rotous, 2020. "A Bayesian longitudinal model for quantifying students’ preferences regarding teaching quality indicators," METRON, Springer;Sapienza Università di Roma, vol. 78(2), pages 255-270, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2011.02330. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.