1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
In the classical experimental design setting, an experimenter E has access to
a population of n potential experiment subjects each associated
with a vector of features x_i. Conducting an experiment with subject i
reveals an unknown value y_i E. E typically assumes some hypothetical
relationship between x_i and y_i, e.g., y_i = β*x_i, 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
c_i 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(I_d + \sum_{i\in S} x_i x_i^T )
under the constraint \sum_{i\in S} c_i ≤ 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 approximately 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.
|
