We consider a setting where resource units are allocated to unit demand agents through reserved categories. Valid allocations must respect quotas, eligibility requirements, and priority constraints in each category and be Pareto efficient. We give a characterization of all valid allocations as solutions to a family of LPs. We use this characterization to study the complexity of many related problems and to give a constant-loss algorithm for an online variant.
Jul 9, 2023
We consider a setting where a principal must pair agents into teams. The success of teams is based on the synergy of their members' types, which are initially unknown and must be inferred by the team performance. We describe team formation policies that achieve near-minimal regret guarantees for different choices of synergy functions.
Dec 9, 2022
We consider estimating the total treatment effect (TTE) in a population with network inteference. The low-order interaction structure of our potential outcomes model allows us to recast this estmiation as a polynomial extrapolation problem. By utilizing a staggered rollout design, we can obtain an unbiased estimator for the TTE that does not require structural knowledge of the causal network.
Nov 28, 2022
We introduce a family of matrices that provably capture any structured matrix with near-optimal parameter and arithmetic operation complexity. We empirically validate that these matrices can be automatically learned within end-to-end pipelines to improve model quality.
Apr 26, 2020
We introduce a parameterization of divide-and-conquer methods that is capable of representing a large class of linear transforms. This generic formulation can automatically learn an efficient algorithm for many such transforms, including the FFT.
Jun 9, 2019
We propose scalable methods to execute counting queries in machine learning applications.
Aug 6, 2018