arXiv Open Access 2020

Adaptive Combinatorial Allocation

Maximilian Kasy Alexander Teytelboym

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

econ.EM stat.ML

Penulis (2)

Maximilian Kasy

Alexander Teytelboym

Format Sitasi

APA MLA BibTeX

Kasy, M., Teytelboym, A. (2020). Adaptive Combinatorial Allocation. https://arxiv.org/abs/2011.02330

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓