Budget feasible mechanisms for experimental design

Abstract

In the classical experimental design setting, an experimenter E has access to a population of n potential experiment subjects i ∈ {1,..., n}, each associated with a vector of features xi ∈ Rd. Conducting an experiment with subject i reveals an unknown value yi ∈ R to E. E typically assumes some hypothetical relationship between xi’s and yi’s, e.g., yi ≈ βTxi, and estimates β from experiments, e.g., through linear regression. As a proxy for various practical constraints, E may select only a subset of subjects on which to conduct the experiment. We initiate the study of budgeted mechanisms for experimental design. In this setting, E has a budget B. Each subject i declares an associated cost ci> 0 to be part of the experiment, and must be paid at least her cost. In particular, the Experimental Design Problem (EDP) is to find a set S of subjects for the experiment that maximizes V (S) = log det(Id + i∈S xix T i) under the constraint i∈S ci ≤ B; our objective function corresponds to the information gain in parameter β that is learned through linear regression methods, and is related to the so-called D-optimality criterion. Further, the subjects are strategic and may lie about their costs. Thus, we need to design a mechanism for EDP with suitable properties. We present a deterministic, polynomial time, budget feasible mechanism scheme, that is ap-proximately truthful and yields a constant ( ≈ 12.98) factor approximation to EDP. By applying previous work on budget feasible mechanisms with a submodular objective, one could only have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. We also establish that no truthful, budget-feasible mechanism is possible within a factor 2 approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression. 1

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 37 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.